[Python] Binary Search(이진 검색)

■

 

이진 검색은 정렬된 배열에서 값을 찾아내는 검색 알고리즘이다. 여기서 정렬된 배열이라는 부분이 아주 굉장히 중요하다. 또한 시간 복잡도는 logn으로 일정하다.

 

그렇다면 이진 검색 과정을 알아보자.

위 그림을 보면 이진 검색 과정을 한번에 이해할 수 있을 것이다.

 

 

 

■■

 

이진 검색을 코드로 구현하는 방법은 대표적으로 [재귀, 반복, 모듈 사용] 총 3가지가 있다.

어려운 알고리즘은 아니니 코드 구현으로 바로 넘어가보자.

 

Recursion

def banarysearch(a:list, target:int):
    def search(left, right):
        if left <= right:
            mid = (left + right) // 2 #찾을 값과 비교할 중간 값 계산
        
            #target이 중간 값보다 크면 중간 값으로 오른쪽에 있을 것이다
            #또 target이 중간 값보다 크거나 작다면 target = mid가 아니므로 mid는 제외시키고 search
            if a[mid] < target:
                return search(mid + 1, right)
            #target이 중간 값보다 작으면 중간 값으로 왼쪽에 있을 것이다
            elif a[mid] > target:
                return search(left, mid - 1)
            else:
                return mid
        else:
            return -1
    return search(0, len(a) - 1)
        
       

Repeat

def binarysearch(a:list, target:int):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        
        if a[mid] < target:
            left = mid + 1
        elif a[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

Recursion과 같아서 주석은 넣지 않았다.

Module

def binarysearch(a:list, target:int):
    index = bisect.bisect_left(a, target)
    
    if index < len(a) and a[index] == target: #예외처리
        return index
    else:
        return -1

bisect_left는 찾는 값의 index를 찾아주고 bisect_right는 찾는 값의 index + 1을 찾아준다.

또한 배열 안에 찾는 값이 없다면 값이 들어갈 index 값을 반환해준다.

 

예를 들어 [1, 2, 3]이라는 리스트가 있는데 4라는 값을 찾고자 한다면

"bisect.bisect_left([1,2,3], 4) = 3"이 된다

배열의 최대 인덱스 2를 뛰어넘는 것이므로 배열에 없다는 말이기도 하다.

 

그래서 위에 Module을 사용한 코드에서도 "index < len(a) and a[index] == target" 이라는 예외처리를 해준 것이다.

 

 

 

■■■

 

마지막으로 몇 가지 더 알아보자.

우선 index()를 사용한 검색과 이진 검색의 시간 복잡도에 대해 간단하게 얘기해볼 것이다.

 

index()와 이진 검색

배열이 크지않을 때는 index()와 이진 검색의 시간 복잡도는 많이 차이가 나지 않는다. 하지만 배열이 커질수록 이진 검색이 더 뛰어난 속도를 나타낸다. 왜냐하면 index()는 Worst Case 시간 복잡도가 n 이고 이진 검색은 시간 복잡도가 logn으로 항상 일정하기 때문이다.

 

여기까지 왔다면 이진 검색이 생각보다 괜찮은 놈이라고 생각이 들 것이다. 또한 이진 검색 모듈인 bisect를 적극 활용하도록 권장하기도 한다.

 

이진 검색의 버그

1980년대에 이진 검색에 대한 오류가 발견되었었다. 그것도 꽤 오랜 시간동안 발견되지 않았던 오류였다.

그 오류는 이 부분이었다.

mid = (left + right) // 2

수학적으로는 전혀 잘못된 점이 없다. 그러나 문제는 최댓값에 제한이 있는 자료형에 있었다.

바로 left + right가 int형의 최댓값 2^31-1을 넘어서면 Overflow가 발생하게 된다는 것이다.

그렇다면 어떻게 수정해야할까...

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

이렇게하면 Overflow를 피할 수 있다.

left + (right - left) / 2 = (left + right) / 2이다.

사칙연산을 할 줄안다면 이해할 수 있을 것이다.