이분 탐색(Binary Search)

Jeonghwan Yoon·2025년 3월 30일

이분탐색이란

정렬된 배열에서 원하는 값을 O(log N) 시간에 찾는 알고리즘
배열의 중간값을 기준으로 왼쪽 또는 오른쪽 절반만 탐색
선형 탐색 O(N)에 비해 훨씬 빠른 성능

동작 원리

중간 인덱스 mid = (left + right) // 2
arr[mid]와 target 비교
- 같으면 → 정답
- 크면 → 왼쪽 탐색
- 작으면 → 오른쪽 탐색
left > right가 될 때까지 반복

구현 예시 (반복문)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 값이 없는 경우

반환값: 찾은 인덱스, 없으면 1

전제 조건 !

배열이 오름차순으로 정렬되어 있어야 함
정렬되지 않은 경우에는 먼저 sort() 필요

시간 복잡도

케이스	시간 복잡도
최선	O(1)
평균	O(log N)
최악	O(log N)

응용 사례

패턴	설명
값 존재 여부 확인	배열 내에 특정 값이 있는지 판단
조건 만족 최솟값/최댓값	매개변수 탐색(Parametric Search)
lower_bound / upper_bound	조건 만족하는 첫 번째/마지막 위치 찾기
정답이 정수 범위일 때	정답 자체를 이분 탐색으로 찾는 경우 자주 등장

재귀 구현 예시

def binary_search_rec(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, right)
    else:
        return binary_search_rec(arr, target, left, mid - 1)

학습 목적으로는 좋지만, 실전에서는 반복문 추천

파라메트릭 서치 패턴 ?

left, right = 조건의 최소값, 최대값
while left <= right:
    mid = (left + right) // 2
    if check(mid):  # 조건을 만족하는가?
        right = mid - 1  # 또는 left = mid + 1 (문제에 따라)
    else:
        left = mid + 1

check() 함수는 문제 조건에 따라 자유롭게 구성
최솟값/최댓값 찾는 문제에서 매우 자주 등장

C언어 전환 시 주의점

요소	설명
배열 길이	`len()` 없음 → 명시적 전달
정수 나눗셈	오버플로우 주의: `(left + right) // 2` 대신 `left + (right - left) // 2` 권장
재귀 깊이	스택 오버플로우 주의
정렬 여부	직접 `qsort()` 또는 구현 필요