이진 탐색 (binary search)

이진 탐색 (혹은 검색, binary search) 는 이미 정렬된 배열에서 타겟을 찾는 검색 알고리즘으로 시간 복잡도가 $O(log n)$이 소요되는 대표적인 로그 시간 알고리즘입니다.

술자리에서 0부터 100까지의 임의의 숫자를 생각해 놓고 업다운을 통해 숫자를 맞추는 게임이 있습니다. 이때, 하나씩 높여가는 것이 아니라 50 -> 25,75 -> 12,37,87 등 숫자 범위의 절반을 줄여가면서 탐색 범위를 점점 좁히게 되죠. 합병정렬처럼 매번 절반으로 쪼개니 $O(\log n)$의 시간 복잡도가 소요됩니다.

절반으로 탐색 범위를 좁혀 계산 횟수가 $\log$ 만큼 줄게 만드는 것은 시간 복잡도 측면에서 굉장히 강력한 성능을 띠게 됩니다. 100까지의 숫자는 7번, 1억까지의 숫자도 27번의 비교로 타겟을 찾아낼 수가 있죠.

그렇다면 왜 이진 탐색은 이미 정렬된 배열에 대해서 수행할까요? 이진 탐색은 일반적으로 특정한 타겟을 찾는 알고리즘이기 때문에 배열의 절반 인덱스의 값이 크냐 작냐에 따라 왼쪽 절반, 오른쪽 절반 중 무엇을  선택할지 재귀적으로 결정하는 알고리즘이기 때문입니다. 이진 탐색은 재귀 혹은 반복 방법으로 구현할 수 있습니다.

파이썬 코드

재귀 방법

def binary_search_with_recursive(array, target):
    ## 재귀적으로 절반을 나눌 divide 함수
    def divide(left, right):        
        if left <= right:
            mid = left + (right - left) // 2
            ## array[mid] 값이 target보다 작다면 오른쪽 절반에 대해 재귀
            if array[mid] < target:
                return divide(left=mid+1, right=right)
            ## array[mid] 값이 target보다 크다면 왼쪽 절반에 대해 재귀
            elif array[mid] > target:
                return divide(left=left, right=mid-1)
            ## array[mid] 값이 target과 같다면 그대로 return
            else:
                return mid
                
        ## 재귀함수 종료 조건
        ## left가 right보다 클 때까지 target이 발견되지 않음
        else:
            return -1
            
    return divide(left=0, right=len(array)-1)
            

합병정렬처럼 절반으로 계속 줄여나가니 재귀로 구현할 수 있습니다. 이 때, 값을 맞출 때까지 재귀 함수를 호출하고 값을 맞춘다면 해당 인덱스를 return, 값을 못 찾았을 경우 -1을 return합니다.

반복 방법

def binary_search_with_iterative(array, target):
    ## 재귀가 아니므로 미리 left, right 값 양 끝으로 설정
    left, right = 0, len(array) - 1
    ## left가 right보다 커질 때까지
    while left <= right:
        ## 절반 인덱스
        mid = left + (right - left) // 2
        ## array[mid]가 target보다 작다면 오른쪽 절반에 대해
        if array[mid] < target:
            left = mid + 1
        ## array[mid]가 target보다 크다면 왼쪽 절반에 대해
        elif array[mid] > target:
            right = mid - 1
        ## array[mid]가 target과 같다면 그대로 return
        else:
            return mid
   
    ## while문을 통과했다면 target에 해당하는 인덱스를 못 찾은 것이므로 -1 return
    return -1

고려 사항

재귀, 반복 방법 모두 루프 안 mid 인덱스를 구하는 과정에서 mid=(left+right)//2가 아니라 mid=left+(right-left)//2 를 사용했습니다.

mid=(left+right)//2 도 사용해도 잘 동작합니다. 하지만 left+right 값이 정수 표현형의 최대값 (32bit)를 넘어갔을 때 overflow가 발생합니다. 이를 방지하기 위해 mid 인덱스를 구할 때는 다음과 같이 사용합니다.

mid = left + (right - left) // 2 

 

홍머스 정리

• 이진 검색은 정렬된 배열에 대해 타겟을 찾는 알고리즘
• 재귀나 반복으로 구현 가능
• $O(\log n)$의 시간복잡도
• 로그는 축복 

참조

• <파이썬 알고리즘 인터뷰>, p515-524