알고리즘 - 이분 탐색, 매개변수 탐색

이분 탐색 (이진 탐색, 매개변수 탐색, 경계 조건)

정렬된 데이터에서 원하는 값을 찾을 때, 처음부터 끝까지 훑는 선형 탐색은 100만 개 자료에서 최악 100만 번을 비교한다. 같은 상황에서 이분 탐색(Binary Search)은 단 20번이면 끝난다. 탐색 범위를 절반씩 잘라 내며 후보를 지수적으로 줄이는 이 단순한 발상이 데이터베이스 인덱스, 표준 라이브러리의 bisect, git의 bisect 명령, 그리고 코딩 테스트 단골 기법인 매개변수 탐색까지 떠받친다. 본 글은 이분 탐색의 정확한 구현과 가장 자주 틀리는 경계 조건, 그리고 최적화 문제를 탐색 문제로 바꾸는 매개변수 탐색을 세심하게 정리한다(출처: 위키백과 — Binary search algorithm). 제가 학교 알고리즘 과제에서 이분 탐색을 처음 짤 때 while left < right로 둘지 left <= right로 둘지 헷갈려 무한 루프에 빠진 적이 있었고, 그 한 번의 실수 이후로는 "이분 탐색의 90%는 경계 조건"이라는 말을 손끝으로 받아들였다.

 

이진 탐색의 원리와 정확한 구현

이진 탐색의 전제 조건은 단 하나, 데이터가 정렬되어 있어야 한다는 것이다. 정렬된 배열에서 가운데 원소와 목표값을 비교하면, 목표가 가운데보다 작은지 큰지에 따라 절반을 즉시 버릴 수 있다. 매 비교마다 후보가 절반으로 줄어들므로 N개 원소에서 최악 log₂N 번의 비교로 끝난다. 100만 개면 약 20번, 10억 개라도 약 30번이다. 이 로그 시간복잡도 O(log N)이 이진 탐색의 본질이다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:                 # 경계: 닫힌 구간 [left, right]
        mid = left + (right - left) // 2 # 오버플로 방지 관용구
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1               # 왼쪽 절반 버림
        else:
            right = mid - 1              # 오른쪽 절반 버림
    return -1                            # 못 찾음

여기서 mid = (left + right) // 2가 아니라 left + (right - left) // 2로 쓰는 이유는 두 인덱스의 합이 자료형 최댓값을 넘는 정수 오버플로를 막기 위함이다. 이 관용구는 자바·C++처럼 정수 범위가 고정된 언어에서 특히 중요하며, 실제로 자바 표준 라이브러리의 이진 탐색에서도 2006년에야 이 버그가 발견되어 수정된 유명한 사례가 있다. 파이썬은 정수 범위가 무한이라 오버플로가 없지만, 습관으로 굳혀 두는 편이 안전하다.

lower_bound와 upper_bound — 이분 탐색의 두 변형

실무와 시험에서 정작 더 자주 쓰이는 것은 "값을 찾는" 기본형이 아니라 "경계를 찾는" 변형이다. 중복 원소가 있는 정렬 배열에서 목표값 이상이 처음 나오는 위치(lower_bound)와 목표값을 초과하는 값이 처음 나오는 위치(upper_bound)를 구하는 것이다. 이 둘만 있으면 "특정 값의 개수", "특정 범위에 든 원소 개수" 같은 질의를 모두 O(log N)에 답할 수 있다.

def lower_bound(arr, target):       # target 이상이 처음 나오는 인덱스
    left, right = 0, len(arr)       # 경계: 반열린 구간 [left, right)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid             # mid 포함 가능성 → 버리지 않음
    return left

기본형이 left <= right에 닫힌 구간을 쓰는 것과 달리 경계 탐색은 left < right에 반열린 구간 [left, right)을 쓴다. 이 차이가 초보자가 가장 자주 헷갈리는 지점이다. 핵심은 "정답 후보를 버리지 않는다"는 불변식을 유지하는 것이며, 위 코드에서 right = mid로 mid를 버리지 않는 이유가 바로 mid가 정답일 수 있기 때문이다. 파이썬은 이 두 함수를 bisect.bisect_left, bisect.bisect_right로 표준 제공하므로 실무에서는 직접 구현할 일이 드물지만, 동작 원리를 모르면 디버깅이 불가능하다.

매개변수 탐색 — 최적화 문제를 결정 문제로

이분 탐색의 진짜 위력은 정렬 배열을 넘어 "답 자체를 이분 탐색하는" 매개변수 탐색(Parametric Search)에서 드러난다. 핵심 발상은 "최댓값을 구하라" 같은 최적화 문제를 "값이 X 이상이 가능한가?"라는 예/아니오 결정 문제로 바꾸는 것이다. 만약 X가 가능하면 X-1, X-2도 당연히 가능하고, X가 불가능하면 X+1, X+2도 불가능하다는 단조성(monotonicity)이 성립하면, 가능/불가능의 경계를 이분 탐색으로 찾을 수 있다.

예컨대 "케이블 N개를 잘라 같은 길이 M개를 만들 때 최대 길이는?"이라는 문제는, "길이 L로 자르면 M개 이상 나오는가?"라는 결정 함수를 만들고 L을 이분 탐색하면 풀린다. L이 클수록 나오는 개수가 줄어드는 단조성 덕분이다.

def cut(cables, length):                 # 결정 함수: length로 자르면 몇 개?
    return sum(c // length for c in cables)

def max_cable(cables, need):
    left, right = 1, max(cables)
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if cut(cables, mid) >= need:     # 충분 → 더 길게 시도
            answer = mid
            left = mid + 1
        else:                            # 부족 → 더 짧게
            right = mid - 1
    return answer

다만 매개변수 탐색이 만능은 아니다. 단조성이 성립하지 않는 문제에는 적용할 수 없으며, 결정 함수 자체가 무거우면 전체 복잡도가 O(log(범위) × 결정함수)로 늘어난다. 또한 정수가 아닌 실수 답을 구할 때는 종료 조건을 반복 횟수나 오차 한계(epsilon)로 잡아야 무한 루프를 피한다. 시험에서는 이진 탐색이 단순 값 찾기로 출제되지만, 실무와 코딩 테스트에서는 이 매개변수 탐색 형태가 압도적으로 자주 나온다는 점이 가장 중요한 차이다.

이진 탐색을 언제 쓰고 언제 피할까

마지막으로 다른 탐색 기법과의 비교로 선택 기준을 정리한다. 한 번 정렬해 두고 여러 번 탐색하는 정적 데이터라면 이진 탐색이 표준이다. 그러나 삽입·삭제가 빈번해 매번 정렬을 다시 해야 한다면, 정렬 비용 O(N log N)이 탐색 이득을 잡아먹으므로 균형 이진 탐색 트리(예: 레드-블랙 트리)나 해시 테이블이 낫다.

상황	권장 자료구조	탐색 복잡도
정렬 후 다회 탐색 (정적)	정렬 배열 + 이진 탐색	O(log N)
삽입·삭제 빈번 + 순서 필요	균형 BST	O(log N)
순서 불필요 + 단순 존재 확인	해시 테이블	O(1) 평균
답 자체가 단조성 가짐	매개변수 탐색	O(log(범위))

흔한 오해 하나를 짚으면 "탐색은 무조건 해시가 가장 빠르다"는 통념인데, 해시는 평균 O(1)이지만 정렬·범위 질의·k번째 원소 찾기를 못 한다. 반면 이진 탐색은 O(log N)이지만 정렬된 구조의 모든 순서 정보를 활용할 수 있다. 즉 "가장 빠른 탐색"이 아니라 "문제가 요구하는 연산의 모양"이 자료구조를 결정한다는 점이, 자료구조와 알고리즘을 함께 공부할 때 비로소 손에 잡히는 핵심이다.

---

메타 디스크립션: 정렬 데이터에서 O(log N)에 값을 찾는 이진 탐색의 정확한 구현과 가장 자주 틀리는 경계 조건, lower_bound·upper_bound 변형, 그리고 최적화 문제를 결정 문제로 바꾸는 매개변수 탐색까지 코드 예시와 함께 세심하게 정리합니다.