for textmining

이진탐색(binary search)

|

이번 글에서는 이진탐색(binary search) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 코드는 이곳을 참고하였습니다. 그럼 시작하겠습니다.

개요

이진탐색 알고리즘이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 알고리즘 특성상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 탐색 대상 데이터 수는 직전의 절반이 되므로 속도가 빠르다는 장점이 있습니다.

이진탐색 알고리즘을 직관적으로 나타낸 그림은 다음과 같습니다(그림 출처 : 영문 위키). 아래와 같이 17개 요소로 이뤄진 리스트에서 7의 위치를 찾는 이진탐색 알고리즘은 화살표 방향처럼 수행이 됩니다.

수행방식

위 그림 예시 기준으로 이진탐색 알고리즘 수행방식을 살펴보겠습니다. 우선 리스트의 중앙을 찾습니다. 요소가 17개이므로 중앙값은 여덟번째(리스트 요소가 $n$개라면 $n/2$를 내림한 값)에 있는 요소(14)가 됩니다. 이 중앙값과 찾고자 하는 값(7)의 크기를 비교합니다. 여기서 찾고자 하는 값이 중앙값보다 작으므로 중앙값보다 큰 값(18, 19, 21, 24, 37, 40, 45, 71)들은 탐색 대상에서 제외합니다.

이번엔 [1, 3, 4, 6, 7, 8, 10, 13, 14]를 새로운 리스트로 보고 같은 작업을 반복 수행합니다. 리스트 중앙을 찾습니다. 새로운 리스트의 요소가 9개이므로 중앙값은 새로운 리스트의 네번째 요소(원래 리스트의 네번째 요소)이며 그 값은 6이 됩니다. 이 중앙값과 찾고자 하는 값(7)의 크기를 비교합니다. 여기서 찾고자 하는 값이 중앙값보다 크므로 중앙값보다 작은 값(1, 3, 4)들은 탐색 대상에서 제외합니다.

이번엔 [6, 7, 8, 10, 13, 14]를 새로운 리스트로 보고 같은 작업을 반복 수행합니다. 리스트 중앙을 찾습니다. 새로운 리스트의 요소가 6개이므로 중앙값은 새로운 리스트의 세번째 요소(원래 리스트의 여섯번째 요소)이며 그 값은 8이 됩니다. 이 중앙값과 찾고자 하는 값(8)의 크기를 비교합니다. 여기서 찾고자 하는 값이 중앙값보다 작으므로 중앙값보다 큰 값(10, 13, 14)들은 탐색 대상에서 제외합니다.

이번엔 [6, 7, 8]을 새로운 리스트로 보고 같은 작업을 반복 수행합니다. 리스트 중앙을 찾습니다. 새로운 리스트의 요소가 3개이므로 중앙값은 새로운 리스트의 두번째 요소(원래 리스트의 다섯번째 요소)이며 그 값은 7이 됩니다. 이 중앙값과 찾고자 하는 값(7)의 크기를 비교합니다. 같으므로 이 중앙값의 위치(원래 리스트의 다섯번째)를 최종 산출물로 반환합니다.

파이썬 구현

이진탐색 알고리즘의 의사코드(pseudo code)는 다음과 같습니다. 아래 코드에서 item은 찾고자 하는 값, sorted_collection는 주어진 정렬된 리스트, left는 이 리스트의 왼쪽 끝 인덱스, right는 오른쪽 끝 인덱스를 의미합니다.

def binary_search(sorted_collection, item):

    left = 0
    right = len(sorted_collection) - 1

    while left <= right:
        midpoint = (left + right) // 2
        current_item = sorted_collection[midpoint]
        if current_item == item:
            return midpoint
        else:
            if item < current_item:
                # 주어진 리스트의 오른쪽 절반은 탐색 대상서 제외
                right = midpoint - 1
            else:
                # 주어진 리스트의 왼쪽 절반은 탐색 대상서 제외
                left = midpoint + 1
    return None

계산복잡도

이진탐색의 계산복잡도 $T(n)$을 따져봅시다. 의사코드를 보면 재귀적으로 자신을 호출하는 부분을 제외하면 상수배 복잡도를 가집니다. left와 right가 같은지, A[left]가 num과 같은지, A[center]가 num과 같은지 등을 따져보고 그 조건에 맞는 몇 가지 기본 연산을 수행하면 되기 때문입니다. 아울러 이진탐색이 반복될 때마다 고려 대상이 되는 리스트의 요소 수는 절반씩 줄어듭니다. 이를 식으로 나타내면 다음과 같습니다.

위 계산식에서 $\log_2n$이 도출되는 이유는 이렇습니다. 최악의 경우를 고려하면 $n/2^i$가 1이 될 때까지 이진탐색을 수행해야 합니다. $n/2^i=1$이므로 로그의 정의에 따라 $i=\log_2n$이 됩니다. big O 표기법에 관련해서는 이곳을 참고하시면 좋을 것 같습니다.

Comments