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

이진 탐색 (Binary Search)

1. 개요

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

2. 예시

3. 시간복잡도

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

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

4. 코드

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