이분 탐색: 답이 남는 경계 찾기

좌표 압축에서 사용한 lower_bound는 단순히 같은 값을 찾는 함수가 아닙니다. 조건을 만족하는 첫 경계를 찾습니다. 이번에는 배열의 경계를 손으로 좁힌 뒤, 같은 원리로 생산 목표의 최소 시간과 물체 사이의 최대 거리를 구합니다.

이분 탐색은 정렬되어 있거나 단조성이 있는 공간에서 답의 후보를 절반씩 줄이는 기법입니다. 단순히 배열에서 값을 찾는 것뿐 아니라, “이 값으로 가능한가?”라는 판정 함수를 만들고 정답 범위를 좁히는 데에도 자주 쓰입니다.

정렬된 배열에서 x 이상의 첫 위치를 찾는다.
가능한 최소 시간을 찾는다.
조건을 만족하는 최대 길이를 찾는다.

반복 중에도 유지되는 조건인 불변식으로 양 끝의 의미를 정합니다. 탐색 구간을 줄일 때도 답이 그 안에 남아 있어야 합니다.

lower_bound

이분 탐색: 답이 남는 구간 따라가기

중복 원소가 있을 때도 같은 값의 첫 위치를 찾는지 살펴보세요. 찾는 값을 최솟값보다 작게, 최댓값보다 크게 바꾸면 경계가 왜 0 또는 배열 길이가 되는지도 확인할 수 있습니다.

lower_bound는 target 이상인 첫 위치를 찾습니다.

a[i] >= target 이 되는 가장 작은 i

이때 탐색 구간을 반열린 구간 [left, right)로 두면 깔끔합니다.

코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

int lowerBound(const vector<int>& a, int target) {
    int left = 0;
    int right = (int)a.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

반복이 끝나면 left == right이고, 그 위치가 답입니다. 모든 원소가 target보다 작으면 a.size()가 반환됩니다.

a = [1, 3, 3, 7, 9]
lower_bound(3) = 1
lower_bound(4) = 3
lower_bound(10) = 5

원문 배열 경계 그림 크게 보기

같은 값이 여러 개 있을 때

lowerBound가 돌려준 위치가 배열 안에 있고 그 값이 target과 같으면 값이 존재합니다. target보다 큰 첫 위치가 필요하면 비교 조건을 a[mid] < target에서 a[mid] <= target으로 바꿉니다. 이것이 upper_bound입니다.

같은 값의 개수는 두 경계의 차이입니다. [1, 3, 3, 7, 9]에서 3의 경계는 1과 3이므로 개수는 2입니다. 두 함수 모두 배열이 오름차순으로 정렬되어 있어야 합니다.

배열 경계와 답의 경계는 같은 문제입니다

lowerBound(a, x)는 항상 0..n을 반환합니다. n도 정상적인 결과이며, 원소가 아니라 배열 끝 경계입니다. 결과가 n인데 a[n]을 읽으면 안 됩니다. 빈 배열에서는 left == right == 0이어서 원소를 한 번도 읽지 않고 0을 반환합니다.

[1,3,3,7,9]에서 3 이상의 첫 위치는 1, 3보다 큰 첫 위치는 3입니다. 두 경계 사이 [1,3)에 3이 두 개 있습니다. 다운로드의 --bounds 모드는 두 경계와 개수를 함께 출력합니다.

배열을 줄이는 동안 [0,left)는 모두 target보다 작고, [right,n)는 모두 target 이상입니다. 아직 확인할 원소는 [left,right)에 남고, 반환할 경계는 left..right 사이에 있습니다. 오른쪽 경계는 포함하지 않는 배열 구간과 구분하세요.

단조 조건

이분 탐색이 가능한 이유는 답 후보가 한 번 기준을 넘으면 그 뒤가 모두 같은 방향으로 유지되기 때문입니다.

false false false true true true

이런 배열에서 첫 true를 찾는 것이 lower_bound의 본질입니다.

반대로 아래처럼 중간에 다시 바뀌면 이분 탐색을 할 수 없습니다.

false true false true true

파라메트릭 서치는 실제 배열 대신 판정 함수 can(x)가 이런 단조성을 가진다고 보고 이분 탐색합니다.

가능한 최소값 찾기

시간 t 안에 작업을 끝낼 수 있는지 판정할 수 있다면 답 자체를 이분 탐색할 수 있습니다. 더 긴 시간을 주었을 때 가능했던 작업이 불가능해지지는 않으므로, 판정 결과는 F F F T T T처럼 한 번만 바뀝니다.

답을 포함하는 [left, right]에서 mid가 가능하면 right = mid, 불가능하면 left = mid + 1로 줄입니다. 시작할 때 right가 가능한 값이어야 합니다.

가능한 최대값 찾기

반대로 요구하는 최소 간격이 커질수록 배치가 어려워지는 문제는 T T T F F F에서 마지막 true를 찾습니다. mid가 가능하면 left = mid, 불가능하면 right = mid - 1입니다.

이때는 mid = left + (right - left + 1) / 2로 올림합니다. [3, 4]에서 내림한 3이 가능하다고 left = 3을 다시 대입하면 구간이 줄지 않기 때문입니다. 아래 최대 거리 구현에서 이 차이를 볼 수 있습니다.

첫 참과 마지막 참을 나란히 보기

그림 크게 보기 · 시간과 거리의 판정 실험

최소 생산 시간은 can(t)가 거짓에서 참으로 바뀌는 첫 위치입니다. 기계 시간이 [2,3,7], 목표가 10개면 11에는 9개, 12에는 11개를 만듭니다. 정확히 10개인 시간이 아니라 10개 이상인 첫 시간을 찾습니다.

최대 간격은 반대로 참에서 거짓으로 바뀌기 직전입니다. 위치 [1,2,4,8,9]에 3개를 놓으면 간격 3은 [1,4,8]로 가능하지만 4는 불가능합니다. 마지막 참을 찾을 때 [2,3]의 mid는 3입니다. 내림한 2로 left = mid를 반복하면 멈추지 않습니다.

두 실험의 탐색 범위는 **양 끝을 포함하는 답 구간 [left,right]**입니다. 앞의 배열 lower_bound가 사용하는 반열린 구간과 코드의 양 끝을 섞지 않습니다. 실험은 먼저 판정한 상태를 보여 주고, 다음 단계에서 경계를 옮깁니다.

예시: 최소 처리 시간

여러 기계가 있고, 각 기계 i는 물건 하나를 만드는 데 time[i]가 걸린다고 하겠습니다. 총 need개를 만드는 최소 시간을 구하려면 시간 t 안에 만들 수 있는 개수를 세면 됩니다.

bool canMake(const vector<long long>& time, long long need, long long t) {
    long long made = 0;
    for (long long one : time) {
        made += t / one;
        if (made >= need) return true;
    }
    return false;
}

long long minimumTime(const vector<long long>& time, long long need) {
    long long left = 0;
    long long right = 1;
    while (!canMake(time, need, right)) {
        right *= 2;
    }

    while (left < right) {
        long long mid = left + (right - left) / 2;
        if (canMake(time, need, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

기계는 하나 이상이고, 각 처리 시간과 목표 수량은 양수라고 가정합니다. 가능한 상한을 모르면 위처럼 두 배씩 늘릴 수 있습니다. 다만 right *= 2와 생산량 누적이 long long을 넘지 않는 입력 범위에서 사용해야 합니다.

예시: 가능한 최대 거리

정렬된 위치 배열 pos에서 물체 k개를 놓되, 인접한 물체 사이 최소 거리를 최대화한다고 하겠습니다.

2 <= k <= pos.size()이고 좌표가 0..10^9라고 가정합니다. 거리 d가 가능하면 그보다 작은 거리도 가능하므로 마지막 true를 찾습니다.

bool canPlace(const vector<int>& pos, int k, int d) {
    int count = 1;
    int last = pos[0];

    for (int i = 1; i < (int)pos.size(); ++i) {
        if (pos[i] - last >= d) {
            count++;
            last = pos[i];
            if (count >= k) return true;
        }
    }
    return false;
}

int maximizeMinimumDistance(vector<int> pos, int k) {
    sort(pos.begin(), pos.end());

    int left = 0;
    int right = pos.back() - pos.front();

    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (canPlace(pos, k, mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

로컬 연습: 생산 목표를 처음 달성하는 시각

기계 i는 time[i] 시간마다 제품 하나를 완성하고 모든 기계가 시각 0부터 동시에 작동합니다. K개 이상을 완성하는 최초의 정수 시각을 구하세요.

입력: N K와 길이 N의 time 배열. 1 <= N <= 200000, 1 <= K <= 10^9, 1 <= time[i] <= 10^9입니다.

출력: 최초 시각을 출력합니다.

예시

3 10
2 3 7

확인 방법: 시각 11에는 5+3+1=9개, 12에는 6+4+1=11개입니다. 작은 입력에서 시각을 하나씩 증가시키는 기준 풀이와 대조합니다. 상한은 min(time)*K이며 생산량 합은 K에 도달하면 판정을 끝내 누적 overflow를 피합니다.

완성 파일로 실행하고 확인하기

C++17 전체 예제 내려받기

c++ -std=c++17 -O2 binary-search.cpp -o lesson
./lesson < input.txt

기본 모드는 앞의 생산 시간 연습을 실행합니다. N K와 N개 처리 시간을 읽고 최초 시각을 출력합니다. 1 ≤ N ≤ 200000, 1 ≤ K ≤ 10^9, 1 ≤ time[i] ≤ 10^9입니다. 예제 출력은 12입니다.

이 범위에서는 답이 min(time) × K ≤ 10^18이고, 두 배로 늘리는 상한도 2^60 이내입니다. 생산량은 목표에 도달하면 반환하므로 덧셈 전 누적값은 K보다 작습니다. 본문 long long 코드가 이 입력 범위에서 안전한 이유입니다. 범위를 바꾼다면 상한 증가와 누적 덧셈부터 다시 확인합니다.

배열의 두 경계는 별도 모드로 실행합니다.

./lesson --bounds < bounds.txt

N target 뒤 이미 오름차순인 N개 정수를 읽습니다. 0 ≤ N ≤ 200000, 모든 값과 target은 -10^9..10^9입니다. lower upper count를 한 줄에 출력합니다. 5 3과 배열 1 3 3 7 9의 출력은 1 3 2, target 10이면 5 5 0, 빈 배열이면 0 0 0입니다. 정렬되지 않은 입력은 거부합니다.

최대 간격 모드는 다음과 같습니다.

./lesson --place < placement.txt

N K와 N개 좌표를 읽고 정렬한 뒤 최대 최소 간격을 출력합니다. 2 ≤ K ≤ N ≤ 200000, 좌표는 0..10^9이고 같은 좌표도 허용합니다. 5 3과 좌표 1 2 4 8 9의 답은 3, 좌표가 모두 같으면 0입니다.

작은 입력에서는 생산 시간을 하나씩 늘리는 풀이, 모든 위치 조합, 배열의 선형 경계 탐색과 비교합니다. 세 모드 모두 필요한 함수와 main을 포함합니다.

기존 이분 탐색 노트에는 과거 구현이 보존되어 있습니다. 일부 조각은 미존재를 -1로 표현하며, 직접 구현의 선언 오타와 [s,e) 주석·반복 경계 불일치도 있습니다. 현재 실습에는 이 강의의 0..n 경계 규약과 검증한 다운로드 파일을 사용하세요.