알고리즘 - 이진 탐색 (Binary Search)

알고리즘 - 이진 탐색 (Binary Search)

오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘으로, 모든 값을 순회해야하는 일반적인 search보다 더 빠르다. 중앙값을 찾는 값에 비교해서 중앙값이 찾는 값보다 크면 왼쪽을 탐색하고 찾는 값보다 작으면 오른쪽을 탐색한다.

 

최악의 경우에도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 탐색 횟수가 logN이다.

따라서 T(N) = O(logN)

 

[ 예시 ]

 

[ 코드 ]

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > target:
            high = mid - 1
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
    return -1