이진 탐색

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 효율적으로 찾는 탐색 알고리즘이다. 이진 탐색은 탐색 범위를 절반씩 줄여 O(log n)의 시간 복잡도를 가진다.

알고리즘 개요

• 정렬된 배열에서만 적용 가능하다.
• 탐색 범위를 절반씩 줄이며, 중간 값을 기준으로 비교한다

이진 탐색 과정

1. 배열의 중간 요소를 선택한다.
2. 찾고자 하는 값과 비교한다.
3. 같다면 탐색 종료, 다르면 왼쪽 또는 오른쪽 절반을 선택하여 반복한다.

이진 탐색 슈도코드

BinarySearch(array, target):
    low = 0
    high = length(array) - 1

    while low ≤ high:
        mid = (low + high) // 2
        if array[mid] == target:
            return mid  # 값 찾음
        elif array[mid] < target:
            low = mid + 1  # 오른쪽 탐색
        else:
            high = mid - 1  # 왼쪽 탐색

    return -1  # 값 없음

이진 탐색 파이썬 코드

반복문 기반 이진 탐색

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 값 찾음
        elif arr[mid] < target:
            low = mid + 1  # 오른쪽 탐색
        else:
            high = mid - 1  # 왼쪽 탐색

    return -1  # 값 없음

재귀 기반 이진 탐색

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # 값 없음

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

시간 복잡도

• 최선의 경우 (Best Case): O(1) (찾고자 하는 값이 처음 선택한 중간 값일 경우)
• 평균 및 최악의 경우 (Average & Worst Case): O(log n)

같은 값이 여러 개일 때 가장 왼쪽 위치 찾기

기본 이진 탐색은 값을 찾는 즉시 그 위치를 돌려주므로, 같은 값이 여러 개 있으면 그중 어느 위치가 나올지 정해져 있지 않다. 처음 나타나는 위치(하한, lower bound)가 필요하면 값을 찾아도 멈추지 않고 위치를 기록한 뒤 왼쪽 구간을 계속 탐색한다. 파이썬 표준 라이브러리의 bisect_left 도 정렬 순서를 지키며 x 를 넣을 수 있는 가장 왼쪽 위치를 돌려준다.

left = 0, right = n - 1, result = -1
while left <= right:
    mid = left + (right - left) / 2      # (left + right) / 2 의 오버플로를 피하는 꼴
    if a[mid] > k:   right = mid - 1
    elif a[mid] == k: result = mid; right = mid - 1   # 찾아도 왼쪽을 더 본다
    else:            left = mid + 1
return result

예를 들어 a = {1, 2, 3, 4}, k = 3 이면

1. left = 0, right = 3, mid = 1 → a[1] = 2 < 3 이므로 left = 2
2. left = 2, right = 3, mid = 2 → a[2] = 3 == 3 이므로 result = 2, right = 1
3. left(2) > right(1) 이므로 끝나고 2 를 돌려준다

a = {1, 3, 3, 3, 5}, k = 3 이면 mid = 2 에서 처음 찾지만 왼쪽을 더 보아 결국 가장 왼쪽 인덱스 1 을 돌려준다. 돌려주는 값은 찾은 값 자체가 아니라 0부터 센 인덱스이다.

이진 탐색의 응용

• 정렬된 데이터에서 탐색
  • 데이터베이스 및 검색 엔진 최적화.

• 이진 검색 트리 (BST)
  • 트리 구조에서 효율적인 검색을 수행.

• 결정 문제 해결
  • 특정 조건을 만족하는 최적의 값을 찾는 데 사용 (예: 파라메트릭 서치).

같이 보기

• 선형 탐색
• 이진 검색 트리
• 분할 정복 알고리즘
• 점프 탐색

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.