[python] 코딩테스트 대비 - 이분검색(결정알고리즘)

문제)

 

답안 코드)

이분 탐색은 시간 복잡도 log_2 N을 보장한다. 

import sys
#sys.stdin=open("input.txt", "r")
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