정렬 데이터에서 이진 탐색을 안전하게 구현하는 법

정렬 전제가 무너지면 탐색 결과도 신뢰할 수 없다

이진 탐색은 정렬된 데이터에서 목표 값을 찾기 위해 후보 구간을 계속 절반으로 나누는 알고리즘이다. 입력이 커질수록 선형 탐색과의 차이가 커지지만, 이 성능은 정렬 또는 판정 함수의 단조성이 보장될 때만 성립한다.

반복 구현의 시간 복잡도는 O(log n), 공간 복잡도는 O(1)이다. 재귀 구현은 호출 스택으로 O(log n)의 공간을 사용한다. 실무에서는 값 자체를 찾는 경우뿐 아니라, 어떤 조건을 처음 만족하는 경계 지점을 찾는 용도로도 자주 쓰인다.

후보 범위를 어떻게 유지할지 먼저 정한다

가장 다루기 쉬운 방식은 반열림 구간 [lo, hi)다. lo는 아직 후보가 될 수 있는 최소 인덱스이고, hi는 후보 범위의 상한이다. 반복 조건을 lo < hi로 두면 구간이 수렴하는지와 종료 시점이 분명해진다.

중간값은 다음 패턴으로 계산한다.

mid = lo + (hi - lo) // 2

이 방식은 단순한 (lo + hi) // 2 계산에서 발생할 수 있는 오버플로를 피한다. 중복 값이 있는 경우에는 첫 번째 이상 위치를 구하는 lower_bound, 첫 번째 초과 위치를 구하는 upper_bound, 마지막 발생 위치처럼 목적에 맞는 경계 규칙을 정해야 한다.

정렬되지 않은 배열이라면 사전 정렬하거나 B-Tree 같은 인덱스 구조를 사용해야 한다. 값 대신 조건을 탐색하는 경우에도 마찬가지다. f(x)가 단조성을 만족할 때만 파라메트릭 서치로 이진 탐색을 적용할 수 있다.

탐색 흐름과 실패 시 반환값

⤢✕

정렬 여부를 확인한 뒤 경계를 초기화하고, 중간값 비교 결과에 따라 한쪽 후보 구간만 남긴다. 일치하는 값을 찾으면 인덱스를 반환하고, 찾지 못한 경우에는 lower_bound에 해당하는 삽입 위치를 반환할 수 있다.

정렬 상태가 확실하지 않다면 실패를 반환하거나 사전 정렬이 필요하며, 이때 시간은 O(n log n)이다. 탐색 중 데이터가 변경될 수 있는 환경에서는 락 또는 스냅샷 격리로 읽기 일관성을 보장해야 한다. 빈 배열, NaN, 비교할 수 없는 타입, 정렬 전제 위반도 별도로 처리 대상이다.

인덱스와 단조 조건에서 만나는 이진 탐색

DB와 스토리지의 B-Tree/B+Tree는 노드 안의 키 배열을 탐색할 때 이진 탐색을 적용할 수 있다. 페이지 내부 탐색은 O(log f)이고, 트리 높이까지 포함한 전체 탐색은 O(log n)이다.

타임스탬프로 정렬된 로그 파일이나 시계열 세그먼트에서는 lower_bound로 시작 오프셋을 구해 이후 선형 스캔 구간을 줄일 수 있다. SLA 모니터링에서는 성능 지표가 ≥ 임계치가 되는 첫 시점을 단조 판정 함수로 찾아낼 수 있다.

체크포인트가 정렬된 배치 처리에서는 최근 성공 지점을 찾아 중복 처리를 줄이는 데 쓸 수 있다. 비용 함수가 단조 조건을 만족한다면 배포 동시성 상한이나 타임아웃 임계값처럼 최소 비용 또는 최대 용량을 구하는 파라메트릭 서치에도 적용된다.

데이터가 n=1,000,000일 때 이진 탐색은 최악 약 20회 비교로 끝난다. 2^20 ≈ 1,048,576이기 때문이다. 데이터 규모가 10배로 증가해도 비교 횟수는 약 3.3회 늘어난다. 중간점 접근 위주의 CPU 캐시 친화적 특성도 있으며, 탐색 지연을 예측하기 쉬워 타임아웃과 슬로우 쿼리 리스크를 낮추는 데 도움이 된다.

선형 탐색과 선택 기준

항목	선형 탐색	이진 탐색
성능(평균/최악)	O(n)	O(log n)
확장성	낮음(선형 증가)	높음(로그 증가)
일관성(결과/지연)	데이터 분포 영향 큼	분포 영향 적음, 단계 수 안정
안정성(에러 민감도)	경계 이슈 적음	경계/오버플로/무한 루프 주의 필요
운영 편의	정렬 불필요, 단순	정렬/인덱스 필요, 초기 비용 존재

Python에서 lower_bound와 정확 일치를 나누기

리스트는 오름차순으로 정렬되어 있어야 하며, 외부 의존성은 없다.

# Python 3.11
from bisect import bisect_left

def binary_search_exact(a, target):
    # 반열림 [lo, hi) 패턴과 동일한 동작
    i = bisect_left(a, target)
    if i != len(a) and a[i] == target:
        return i
    return -1  # not found

def lower_bound(a, target):
    return bisect_left(a, target)

# 수동 구현(오버플로 없는 mid, [lo, hi) 불변식)
def lower_bound_manual(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

if __name__ == "__main__":
    arr = [1, 3, 3, 5, 8, 13]
    print(binary_search_exact(arr, 5))   # 3
    print(lower_bound(arr, 4))          # 3 (삽입 위치)
    print(lower_bound_manual(arr, 3))   # 1 (첫 3의 위치)

bisect_left는 lower_bound와 같은 위치를 반환한다. 정확한 일치 여부가 필요할 때는 반환 인덱스가 배열 범위 안에 있는지와 해당 값이 목표 값인지 추가로 확인한다.

Java에서 반열림 경계를 유지하는 구현

배열 역시 오름차순 정렬이 전제이며, 외부 라이브러리는 필요하지 않다.

// Java 17
public class BinarySearch {
    // lower_bound: 첫 번째 a[i] >= target의 인덱스 반환
    public static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length; // [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2; // 오버플로 방지
            if (a[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // 정확 일치: 존재 시 인덱스, 없으면 -1
    public static int indexOf(int[] a, int target) {
        int i = lowerBound(a, target);
        return (i < a.length && a[i] == target) ? i : -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 5, 8, 13};
        System.out.println(indexOf(arr, 5)); // 3
        System.out.println(lowerBound(arr, 4)); // 3
    }
}

갱신 비용과 동시성까지 포함해 판단한다

[lo, hi) 구간과 불변식을 코드와 문서에 명시하고, 종료 조건은 lo < hi로 유지하는 편이 안전하다. 탐색 실패 시 삽입 위치를 반환하면 삽입과 범위 쿼리의 후속 처리에도 활용할 수 있다.

정렬 또는 인덱스를 처음 구축하는 데는 O(n log n)의 비용이 필요하다. 갱신이 잦은 워크로드에서는 이 유지 비용을 함께 고려해야 한다. 대량 데이터에서는 분기 예측 실패에 따른 미세한 CPU 패널티가 생길 수 있으므로 B-Tree 같은 블록 최적화 구조가 더 적합할 수 있다.

동시성 환경에서는 Immutable 구조로 입력 스냅샷을 확보하거나 읽기 락을 사용해 탐색 중 데이터가 바뀌지 않도록 해야 한다. 이 전제가 지켜질 때 이진 탐색은 인덱스 구조, 타임시리즈 시작점 계산, 파라메트릭 서치에 안정적으로 적용할 수 있다.