[Python] 이분탐색 시간복잡도

이분탐색의 원리

Up & Down 게임을 떠올리면 이해하기가 쉽다.
1~100 까지의 수가 있다고 가정할 때, 특정한 수를 정해놓고 그 수보다 up인지 down인지를 계속해서 계산한다.
그리고 중간 값을 통해 범위를 좁혀나간다.

 

시간복잡도

시간 복잡도는 O(logN)이다.

 

low, high
mid = (low + high) /2

#수가 mid 보다 작을 때
high = mid - 1

#수가 mid보다 클 때
low = mid + 1

#key = mid 이면 끝!