이진 탐색

정렬된 배열에서 탐색 범위를 절반씩 줄여가며 값을 찾는 알고리즘입니다.

동작 과정

A = [1, 3, 5, 7, 9, 11, 13]   target = 11

lo=0, hi=6
  mid=(0+6)/2=3 → A[3]=7  < 11 → 오른쪽 절반으로
  [ _, _, _, _, 9, 11, 13 ]
lo=4, hi=6
  mid=(4+6)/2=5 → A[5]=11 = 11 → 발견, index 5

범위 크기: 7 → 3 → 1
비교 횟수: 3회 (선형 탐색이면 최악 7회)

lower bound / upper bound

"찾기"보다 실전에서 더 자주 쓰이는 형태입니다.

A = [1, 3, 3, 3, 7]   target = 3

lower bound: 3 이상이 처음 나오는 위치 → index 1
upper bound: 3 초과가 처음 나오는 위치 → index 4

              0  1  2  3  4
         A = [1, 3, 3, 3, 7]
                 ↑        ↑
            lower(1)   upper(4)

upper - lower = 3  → 값 3의 개수

구현

// 값의 위치 찾기 — 없으면 -1
int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // (lo + hi) / 2 는 오버플로 위험
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// lower bound — target 이상이 처음 나오는 위치
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;        // hi는 길이 (닫힌 구간이 아님)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// upper bound — target 초과가 처음 나오는 위치
int upperBound(int[] a, int target) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;   // <= 로 바뀌는 것만 차이
        else hi = mid;
    }
    return lo;
}

두 함수는 비교 연산자 하나만 다릅니다. 이 차이가 "처음 위치"와 "마지막 다음 위치"를 가릅니다.

표준 라이브러리로는 Arrays의 Arrays.binarySearch, Collections의 Collections.binarySearch가 있지만, 값이 없을 때 -(삽입위치)-1을 반환하고 중복 값에서 어느 인덱스를 줄지 보장하지 않아 lower/upper bound 용도로는 직접 구현하는 편이 안전합니다. 중복을 다루지 않는다면 TreeSet의 ceiling/floor도 선택지입니다.

복잡도

구분복잡도근거
시간O(log N)매 비교마다 탐색 범위가 절반으로 줄어듦
공간O(1)반복문 구현. 재귀로 쓰면 O(log N) 스택

단, 정렬이 전제입니다. 정렬되지 않은 배열이라면 정렬에 O(N log N)이 먼저 들어갑니다. 한 번 탐색할 뿐이라면 선형 탐색 O(N)이 더 빠릅니다.

주의사항

핵심 정리

CSLOG에서 보기