이진 탐색

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

1 알고리즘 개요

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

2 이진 탐색 과정

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

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  # 값 없음

4 이진 탐색 파이썬 코드

반복문 기반 이진 탐색

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)

5 시간 복잡도

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

6 이진 탐색의 응용

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

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

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

7 같이 보기

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

8 참고 문헌

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