이분 탐색 (Binary Search)

이분 탐색(Binary Search)은 정렬된 배열에서 탐색 범위를 절반씩 잘라내며 답을 찾는 알고리즘이다. 비교 한 번에 후보의 절반이 사라지므로 원소가 n개일 때 O(log n)에 끝난다. 원소가 100만 개여도 20번, 10억 개여도 30번이면 충분하다.

코딩테스트에서 이분 탐색이 중요한 진짜 이유는 따로 있다. "정렬된 배열에서 값 찾기"로 나오는 문제는 오히려 드물고, 정렬된 배열이 문제에 아예 등장하지 않는데도 이분 탐색으로 푸는 유형이 훨씬 자주 나오기 때문이다. 이 글은 기본 형태에서 시작해 그 응용 유형까지 이어서 다룬다.

개념과 원리

정렬된 배열의 가운데 원소 하나를 목표 값과 비교하면 세 갈래가 나온다. 같으면 끝이고, 가운데 값이 목표보다 크면 목표는 왼쪽에만 있을 수 있으며, 작으면 오른쪽에만 있을 수 있다. 어느 쪽이든 단 한 번의 비교로 후보의 절반을 근거 있게 버린다는 것이 전부다.

여기서 꼭 짚고 갈 것이 하나 있다. 이분 탐색에 정말로 필요한 조건은 "정렬"이 아니라 한 번만 뒤집히는 성질이다. 배열이 정렬되어 있으면 "arr[i]가 목표보다 작은가?"라는 질문의 답이 [참, 참, 참, 거짓, 거짓]처럼 딱 한 번만 바뀐다. 이분 탐색이 쓰는 건 정렬 자체가 아니라 바로 이 성질이다.

그래서 정렬된 배열이 없어도, 어떤 질문의 답이 한 번만 뒤집히기만 하면 이분 탐색을 쓸 수 있다. 뒤에 나올 파라메트릭 서치가 정확히 이 이야기이고, 코딩테스트에서 이분 탐색이 나오는 방식의 대부분이 이쪽이다.

동작 과정

1. 탐색 범위의 양 끝 low, high를 배열의 처음과 끝 인덱스로 둔다.
2. 범위가 남아 있는 동안 가운데 mid = low + (high - low) // 2를 계산한다.
3. arr[mid]와 목표를 비교해 같으면 mid를 반환한다.
4. arr[mid]가 목표보다 작으면 low = mid + 1, 크면 high = mid - 1로 옮긴다.
5. 범위가 비면 배열에 목표가 없다는 뜻이므로 실패를 반환한다.

경계 찾기 — lower bound와 upper bound

실전에서 더 자주 쓰는 쪽은 값을 찾는 이분 탐색이 아니라 경계를 찾는 이분 탐색이다. 중복이 있는 배열에서 "이 값이 처음 등장하는 위치"나 "이 값보다 큰 첫 위치"를 알아야 하는 상황이 훨씬 많기 때문이다.

• lower bound: target 이상인 첫 인덱스. target이 없으면 삽입해야 할 자리를 가리킨다.
• upper bound: target 초과인 첫 인덱스.

경계 탐색은 값을 찾자마자 멈추지 않고 범위가 한 점으로 좁혀질 때까지 끝까지 진행한다는 점이 일반 이분 탐색과 다르다. 그래서 반복문 조건도 low < high이고, high의 초기값도 len(arr) - 1이 아니라 len(arr)이다. 모든 원소가 target보다 작을 때 "배열 끝"이라는 답을 표현해야 하기 때문이다.

시간 복잡도

구분	복잡도	설명
탐색 1회	O(log n)	n = 100만이면 약 20번, n = 10억이면 약 30번 비교
정렬이 선행되는 경우	O(n log n)	정렬 비용이 지배적
공간 (반복문)	O(1)	인덱스 변수 몇 개만 사용
공간 (재귀)	O(log n)	호출 스택 깊이만큼

탐색을 딱 한 번만 한다면 정렬 없이 순차 탐색하는 O(n)이 오히려 빠르다. 이분 탐색이 이득을 보는 지점은 같은 배열에 질의가 여러 번 들어올 때다. 질의가 q번이면 순차 탐색은 O(nq), 이분 탐색은 O(n log n + q log n)이다. n과 q가 각각 10만이면 전자는 100억 번, 후자는 약 340만 번이라 시간 초과와 통과를 가르는 차이가 된다.

구현 코드 예시

def binary_search(arr, target):
    """target의 인덱스를 반환한다. 없으면 -1."""
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2   # (low + high) // 2 는 오버플로 위험
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


def lower_bound(arr, target):
    """target 이상이 처음 나오는 인덱스. 없으면 len(arr)."""
    low, high = 0, len(arr)          # high가 len(arr)인 것에 주의
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid               # mid는 답 후보이므로 버리지 않는다
    return low


def upper_bound(arr, target):
    """target 초과가 처음 나오는 인덱스."""
    low, high = 0, len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= target:       # lower_bound와 부등호 하나만 다르다
            low = mid + 1
        else:
            high = mid
    return low


def count_of(arr, target):
    """정렬된 배열에서 target의 개수를 O(log n)에 센다."""
    return upper_bound(arr, target) - lower_bound(arr, target)

실제 코딩테스트에서는 직접 구현할 필요가 없다. 파이썬은 bisect.bisect_left가 lower bound, bisect.bisect_right가 upper bound다. 자바는 Arrays.binarySearch가 있지만 중복이 있을 때 어느 인덱스를 줄지 보장하지 않으므로, 경계가 필요하면 직접 짜는 편이 안전하다. 다만 면접에서는 손으로 쓸 수 있어야 하고, 두 함수의 차이가 <와 <= 하나뿐이라는 점을 설명할 수 있어야 한다.

def min_capacity(tasks, days):
    """하루에 x만큼 처리할 때 days일 안에 tasks를 다 끝내는 최소 x."""

    def possible(x):
        need, cur = 1, 0            # need: 걸리는 날짜
        for t in tasks:
            if cur + t > x:         # 오늘 못 담으면 다음 날로
                need += 1
                cur = 0
            cur += t
        return need <= days

    lo, hi = max(tasks), sum(tasks)  # 답이 존재할 수 있는 최소·최대 범위
    while lo < hi:
        mid = (lo + hi) // 2
        if possible(mid):
            hi = mid                 # 가능하면 더 줄여본다
        else:
            lo = mid + 1             # 불가능하면 늘려야 한다
    return lo

def search_rotated(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid

        if arr[low] <= arr[mid]:                    # 왼쪽 절반이 정렬됨
            if arr[low] <= target < arr[mid]:       # target이 그 안에 있으면
                high = mid - 1                      # 왼쪽으로
            else:
                low = mid + 1
        else:                                       # 오른쪽 절반이 정렬됨
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1