1. 이분검색

[문제설명]

이분검색 학습을 위한 문제

 

[문제 이분검색]

 

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요

-입력설명

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

-출력설명

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

 

-입력예제1

8 32

23 87 65 12 57 32 99 81

 

-출력예제1

3

 

[풀이]

8개의 수를 오름 차순으로 정렬한 다음 8개의 수 중 한개의 수인 32 가 주어지면 이분 검색으로 32가 정렬 된 상태에서 몇번째 

 

[소스코드]

import sys
sys.stdin=open("input.txt", "rt")

n, m=map(int, input().split())
nums=list(map(int, input().split()))
nums.sort()
lt=0 #0번 인덱스
rt=n-1 #오른쪽 맨끝
while lt<=rt: #lt가 rt보다 커지면 탐색이 종료
    mid=(lt+rt)//2
    if nums[mid]==m:
        print(mid+1)
        break
    elif nums[mid]>m:
        rt=mid-1
    else :
        lt=mid+1

 

[output]

 

*본 문제는 인프런 김태원 강사님의 파이썬 알고리즘 문제풀이 강의에 기반합니다.