이분 탐색

문제 )

1 4 5 6 7 9 11 16 43 59 의 오름차순이 있을 때 7의 위치는?

 

lt = 0, rt = n-1 을 설정

 

while lt <= rt :

mid = (lt+rt)//2

로 지정 후 

if a[mid] == m:

     print(mid+1) 을 한 후 break 해주고

이것이 아닌 a[mid]가 목표 값 7 보다 크다면 rt = mid-1 을 해서 범위를 좁혀준다

이것이 아닌 a[mid[가 목표 값 7 보다 작다면 lt = mid + 1을 해서 범위를 좁힌다.

 

이렇게 해서 원하는 값을 찾으면 된다. 다음은 전체 코드이다.

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
lt = 0
rt = n-1
while lt <= rt:
    mid = (lt+rt)//2
    if a[mid] == m:
        print(mid+1)
        break
    elif a[mid]>m:
        rt = mid-1
    else : 
        lt = mid + 1