이진 탐색(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)

이진 탐색의 응용

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

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

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

같이 보기

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

참고 문헌

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