[이진 탐색] 시작하기 전에 정리하는 패턴 3가지와 자주 쓰는 계산법

카테고리: 이진탐색 이 글은 문제 하나를 다루는 글이 아니라, 이 카테고리를 시작하기 전에 알아야 할 개념 전체를 한 번에 정리한 글이다. 앞으로 이 카테고리의 다른 글들은 이 글에서 정리한 패턴을 전제로, 그 문제에서만 있었던 시행착오를 다룬다.

이진 탐색이란?

정렬된 데이터에서 값을 찾을 때, 처음부터 하나씩 확인하면(선형 탐색) 최악의 경우 데이터 개수만큼(O(n)) 봐야 한다. 이진 탐색은 “가운데를 한 번 확인해서 절반을 통째로 버린다”는 전략으로 이걸 O(log n)으로 줄인다.

핵심 3문장:

1. 정렬된 데이터(또는 정렬된 성질을 가진 값의 범위)에서 가운데(mid)를 확인한다.
2. 확인 결과로 왼쪽 절반 또는 오른쪽 절반을 통째로 버릴 수 있다는 걸 판단한다.
3. 후보가 하나 남을 때까지 반복한다.

가장 중요한 불변식 — “확인한 mid는 다음 범위에 남기지 않는다”

이진 탐색이 매번 절반씩 줄어드는 이유는 이 한 가지 규칙 때문이다.

mid를 확인해서 “이건 정답이 아니다” 또는 “이건 정답일 수 없는 쪽이다”라고 판단했으면, 그 mid는 다음 탐색 구간에서 반드시 제외한다.

left = mid, right = mid처럼 확인이 끝난 mid를 범위에 그대로 남겨두면, left와 right가 인접한 상황에서 mid가 계속 같은 값으로 재계산되어 무한 루프에 빠진다. 그래서 범위를 좁힐 땐 mid+1 / mid-1로 확실히 제외하는 게 기본이다 (단, 패턴 2·3처럼 “이 mid가 여전히 답의 후보”인 경우는 예외 — 아래에서 구분).

패턴 3가지

이진 탐색 코드는 실질적으로 이 3가지 모양 중 하나다. 어떤 패턴인지는 “mid가 정답 후보로 남을 수 있는가”로 구분한다.

패턴 1 — 값 존재 확인 (기본형)

arr[mid] == target처럼 “정확히 일치”하는 경우가 있는 탐색. 맞으면 즉시 종료, 아니면 양쪽 다 mid를 확실히 버린다.

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return -1; // 못 찾음

• 루프 조건: left <= right
• 종료 후 left는 “이 값이 있었다면 들어갈 위치”(삽입 위치)가 된다.

패턴 2 — 왼쪽 경계 찾기 (최솟값 조건 / lower bound / 파라메트릭 서치)

“조건을 만족하는 값 중 최솟값”을 찾는다. 문제에 “최댓값의 최솟값” 같은 표현이 보이면 이 패턴이다. mid가 조건을 만족하면 “더 줄여볼 수 있는 후보”이므로 범위에 남겨야 한다.

int left = lowerBound, right = upperBound;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (isPossible(mid)) {
        right = mid;       // mid가 조건을 만족 -> 여전히 후보일 수 있으니 남긴다
    } else {
        left = mid + 1;    // mid로는 불가능 -> 확실히 버린다
    }
}
return left; // == right, 최솟값

• 루프 조건: left < right (같아지는 순간 정답 확정)
• right = mid로 남기기 때문에, mid 계산에서 내림(기본 /2)을 그대로 써도 안전하다.

패턴 3 — 오른쪽 경계 찾기 (최댓값 조건 / upper bound)

“조건을 만족하는 값 중 최댓값”을 찾는다. 패턴 2와 반대로 mid가 조건을 만족하면 그걸 남기고, 방향이 뒤집힌다.

int left = lowerBound, right = upperBound;
while (left < right) {
    int mid = left + (right - left + 1) / 2;  // 올림! 안 하면 무한루프
    if (isPossible(mid)) {
        left = mid;         // mid가 조건을 만족 -> 여전히 후보
    } else {
        right = mid - 1;    // 불가능 -> 버린다
    }
}
return left; // == right, 최댓값

• left = mid로 남기는 패턴이라, mid를 내림으로 계산하면 left와 right가 인접할 때(left+1==right) mid가 항상 left로 계산되어 값이 안 줄어들고 무한 루프에 빠진다. 그래서 올림 계산((left+right+1)/2, 오버플로우 방지형은 left + (right-left+1)/2)을 반드시 써야 한다.
• 아직 실전에서 다루지 않았고, “조건 만족하는 것 중 최댓값” 유형이 나오면 그때 문제로 다시 짚는다.

탐색 범위(left/right)의 상한을 정하는 법 (2026-09-14 추가)

파라메트릭 서치에서 가장 많이 틀리는 지점 중 하나가 탐색 상한(right)을 뭘로 잡을지다. “배열의 최댓값”을 습관적으로 쓰면 틀릴 수 있다 — 문제마다 “이 값이면 무조건 성공한다”는 근거가 따로 있어야 한다.

• LC875 (Koko Eating Bananas): right = max(piles)가 맞다. 먹는 속도가 가장 큰 무더기보다 빠르면 그 무더기를 1시간에 다 먹으니, 그 이상 속도는 의미가 없다. 원소들이 서로 독립이라 최댓값이 곧 상한이 된다.
• LC1011 (Capacity To Ship Packages): right = max(weights)는 틀렸다. 하루에 여러 짐을 동시에 실을 수 있어서, 최악의 경우(모든 짐을 하루에 다 실어야 하는 상황) capacity가 배열의 최댓값을 넘어설 수 있다. 이럴 땐 right = sum(weights)가 진짜 상한이다 — “이 capacity면 하루 만에 전부 실을 수 있다”는 확실한 값.

판단 기준: 원소들이 서로 독립적으로 처리되는 문제면 최댓값이 상한이 될 때가 많고, 원소들을 순서대로 그룹으로 묶어야 하는 문제(그리디 시뮬레이션이 필요한 유형)면 합계가 상한이 될 가능성이 높다. 둘 다 아니라면, “이 상한 값을 넣었을 때 조건을 항상 만족하는가”를 예제로 직접 검증해봐야 한다.

mid 계산 꿀팁

• mid = (left + right) / 2는 쓰지 않는다. left, right가 둘 다 int 최댓값 근처로 크면 left + right가 오버플로우로 음수가 될 수 있다.
• 항상 mid = left + (right - left) / 2 (패턴 2, 기본형)로 쓴다.
• 패턴 3(오른쪽 경계)만 올림이 필요: mid = left + (right - left + 1) / 2.

올림 나눗셈 (파라메트릭 서치에서 자주 등장)

“시간”, “묶음 개수”처럼 나머지를 버릴 수 없고 올림해야 하는 계산에는 이 공식을 쓴다.

long ceilDiv = (x + k - 1) / k;   // x를 k로 나눈 값을 올림

파라메트릭 서치를 알아채는 신호

문제 지문에 아래 표현이 보이면 패턴 2(또는 3)를 의심한다.

• “최댓값의 최솟값” / “최솟값의 최댓값”
• “~할 수 있는 최소 속도/용량/시간을 구하라”
• 정렬된 배열이 아니라 “답이 될 수 있는 값의 범위” 자체가 주어짐 (예: 속도 1~최댓값, 용량 최댓값~합계)

판정 함수(isPossible(mid))를 먼저 설계하고, 그 함수가 단조성(어떤 값 이상/이하부터는 항상 참 또는 항상 거짓)을 갖는지 확인하는 게 첫 단계다.

자주 쓰는 라이브러리

• Arrays.binarySearch(arr, key) — 정렬된 배열에서 값 탐색. 없으면 -(삽입위치)-1을 반환한다 (음수라 그대로 못 쓰고 변환 필요).
• Collections.binarySearch(list, key) — 리스트 버전, 동작 방식은 동일.
• 실전에서는 라이브러리보다 직접 left/right/mid 루프를 짜는 문제가 훨씬 많다 (조건 판정 함수가 필요한 경우가 대부분이라).

디버깅 팁

무한 루프가 의심되면 반복마다 left/right/mid 값을 출력해서, 이 값들이 실제로 좁혀지고 있는지부터 눈으로 확인한다. 대부분의 원인은 “확인이 끝난 mid를 범위에 남겨야 하는데 안 남겼다” 또는 그 반대다.