범위를 반씩 좁혀가는 이진탐색

이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

def binary_search(array, target, start, end):
   while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

이진 탐색 알고리즘은 가급적 외우고, 탐색 범위가 2000만을 넘어가면 접근해보는 것을 권한다.