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

이진 검색?

이진 검색은 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.

위와 같은 배열에서 89를 검색한다고 가정한다.

이 배열의 가운데 값은 77이다.

이 때 89는 77보다 크므로, 오름차순인 이 배열에서 89는 77보다 뒤에 있음을 확인할 수 있다.

따라서 77 이전의 요소는 탐색할 필요가 없다.

뒷 부분에서 가운데 값은 98이다.

89는 98보다 작으므로, 98 뒷 요소는 탐색할 필요가 없다.

다시, 중앙의 원소인 89에 주목한다.

이는 키 값과 일치하므로, 검색을 종료한다.

 

+) 89가 중앙 원소인 이유?

89의 인덱스: 6

92의 인덱스: 7

89와 92의 중간 인덱스 계산: (6 + 7) // 2 = 6

 

 

과정을 좀 더 상세하게 보자.

arr[mid] == key이면 검색이 성공한 것!

 

arr[mid] < key 일 때,

검색 범위가 arr[mid + 1] ~ arr[right]로 좁혀진다.

따라서, left 값을 mid + 1로 업데이트 한다.

 

arr[mid] > key 일 때,

검색 범위가 arr[left] ~ arr[mid - 1]로 좁혀진다.

따라서, right 값을 mid - 1로 업데이트 한다.

 

종료 조건은 다음과 같다.

• arr[mid]와 key가 일치 (성공)
• 검색 범위가 더 이상 없는 경우 (실패)

시간 복잡도는 O(log n)이다.

(선형 검색의 시간복잡도가 O(n)이라는 것을 생각하면, 이진 검색이 더 효율적이라는 사실을 알 수 있다.)

 

구현 with 파이썬

def binarySearch(arr, key):
    left = 0
    right = len(arr) - 1

    while True:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid  # 성공
        elif arr[mid] < key:
            left = mid + 1
        elif arr[mid] > key:
            right = mid - 1
        if left > right:
            return -1   # 실패