[Algorithm] 이진 탐색(Binary Search) 알고리즘

Binary Search

Idea

이진 탐색은 정렬된 배열이 주어질 때, 리스트의 중간값과 비교하면서 반씩 제외하며 원하는 값을 찾아가는 과정입니다.

주의할 점은, 이진 탐색 알고리즘은 정렬된 배열에만 적용 가능하다는 점입니다. 따라서 정렬되어있지 않다면 성능이 우수한 퀵 정렬을 통해 약 O(nlogn)의 시간을 들여 정렬을 한 뒤 이진 탐색 알고리즘을 적용해야 합니다.

이진 탐색의 과정을 살펴보면 아래와 같습니다.

1. 중간 인덱스(middle)를 구한다. (첫번째 인덱스 + 마지막 인덱스) / 2
2. 찾을 값(target)이 middle보다 작은 경우, middle과 그 이후 인덱스들을 검색 범위에서 제외한다.
3. target이 middle보다 큰 경우, middler과 그 이전 인덱스들을 검색 범위에서 제외한다.
4. target과 middle에 해당하는 값이 같을 때까지 반복하고, 같다면 middle을 리턴한다.

 

이를 코드로 구현하면 아래와 같습니다.

Code

# data는 정렬된 리스트이다.
def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid  # 탐색 결과
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

 

Time complexity

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

위와 같이 이진 탐색을 진행하게 되면, 마치 이진 트리에서 높이를 하나씩 내려가며 찾는 것과 같습니다.

위에서 중간값과 찾는 값을 비교하고, 작다면 왼쪽으로 크다면 오른쪽으로 검색 범위를 좁혀갔습니다. 이는 곧 위 이진 트리에서 자식 노드로 하나씩 내려가는 것과 같죠,

따라서, 시간 복잡도는 트리의 높이인 O(logn)입니다.

이를 좀 더 자세히 따져보면, 전체 데이터 개수를 N이라고 할 때, 탐색에 따라 남은 수를 구하면 아래와 같습니다.
1) 첫 번째 탐색 후 절반만 남아 남은 수 => N/2개.

2) 두 번째 탐색에서 다시 절반만 남아 남은 수 =>  N/2 * 1/2개.

3) 세 번째 탐색에서 다시 절반이 남아 남은 수 => N/2 * 1/2 * 1/2개

따라서 이를 정리하면 k번째 탐색에서 남은 데이터 수는 (1/2)^k * N 입니다.

Worst case를 생각해보면, 남은 데이터 수가 1이 될 때까지 탐색을 지속하는 경우가 될 것입니다.
따라서, (1/2)^k * N = 1이고, 이를 정리하면 k = log2 N이 됩니다.

사실, 남은 데이터 수가 1이 될 때까지 탐색을 지속한다는 것은, 곧 트리의 맨 밑까지 탐색을 지속한다는 것이기 때문에 트리의 높이만큼 탐색을 실시하는 것과 같습니다.