이진 탐색 불변식과 경계 탐색 패턴

이진 탐색 문제는 값 찾기보다 경계 찾기 형태로 더 자주 나옵니다. 처음에는 코드가 짧아 보여도 구간 규칙을 섞는 순간 오프바이원과 무한 루프가 바로 생깁니다. 그래서 템플릿 암기보다 불변식 고정이 우선입니다.

해결 순서는 단순합니다. 구간 표현을 하나로 고정하고, 판정 함수의 단조성을 확인한 뒤, 같은 규칙으로 끝까지 밀어붙입니다. 아래에서는 그 과정을 경계 탐색 기준으로 정리합니다.

이진 탐색 경계 탐색 불변식 설계 맵

핵심 개념 맵: 이분 탐색 불변식

이진 탐색은 코드 자체보다 전제 세 가지를 정확히 고정하면 안정적으로 구현할 수 있습니다. 우선 본인 코드에서 쓰는 구간 표기([], [))를 한 줄로 적어 두고 시작하세요.

단조성은 인덱스가 커질수록 판정 결과가 한 번만 바뀌는 성질입니다. ok(x)가 false...false,true...true 형태(또는 반대 형태)를 유지해야 이진 탐색 경계가 생깁니다. 예를 들어 처리 속도 v가 커질수록 시간 내 완료 가능이 한 번만 false -> true로 바뀌면 경계 탐색이 가능합니다.

구간 불변식은 반복 중에도 "정답이 현재 구간 안에 있다"는 약속입니다. 반복문 각 단계가 끝난 뒤에도 정답 후보 집합이 탐색 구간에 남아 있어야 무한 루프와 오프바이원을 피할 수 있습니다. [lo, hi) 규칙이라면 반복이 끝날 때까지 lo <= ans < hi가 계속 유지되어야 합니다.

판정 함수는 후보 값이 정답 조건을 만족하는지 알려주는 결정 함수입니다. 가능/불가능 판정이 단조성을 가지면 판정 함수 기반으로 최소값 또는 최대값 경계를 찾을 수 있습니다. ok(mid)=mid 속도로 시간 내 완료 가능한가처럼 정의하면 최소 가능 속도를 이진 탐색으로 계산할 수 있습니다.

경계 탐색 설계가 실무에서 중요한 이유

이진 탐색 실패의 대부분은 알고리즘을 몰라서가 아닙니다. lo, hi, mid 갱신 규칙이 서로 다른 템플릿이 섞여 무한 루프나 오프바이원 오류가 생겨서 실패합니다.

또한 문제는 정렬 배열 탐색처럼 보이지 않아도 가능/불가능 판정 함수로 바꾸면 이진 탐색으로 풀리는 경우가 많습니다. 이 관점 차이가 난이도 차이를 만듭니다.

경계값 오답 재현으로 재확인하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

lower_bound를 작은 배열로 직접 추적합니다.

배열: [1, 2, 2, 2, 4, 7]
타깃: 2

mid 값을 보며 arr[mid] < target이면 오른쪽으로 이동합니다.
그렇지 않으면 mid도 후보이므로 왼쪽 경계를 줄입니다.
루프 종료 시 lo가 첫 번째 >= target 위치가 됩니다.
중요한 기준은 "답은 항상 [lo, hi) 안에 있다"는 불변식 유지입니다.

이분 탐색 적용 관찰 기준

아래 질문에 모두 예라고 답할 수 있으면 이진 탐색 후보입니다.

탐색 구간에 순서가 존재하는가?
판정 결과가 단조한가?
구간을 절반씩 버리는 것이 안전한가?
경계값을 반환하는 요구인가?

반대로 단조성이 없다면 이진 탐색을 강행하면 안 됩니다.

경계 탐색: `lower_bound` 구현

문제 의도: 첫 번째 >= target 인덱스를 찾는 이진 탐색 템플릿을 고정합니다.
입력 예시: arr=[1,2,2,2,4,7], target=2
출력 예시: 1

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int lowerBound(const vector<int>& arr, int target) {
    int lo = 0;
    int hi = static_cast<int>(arr.size()); // [lo, hi)

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    return lo;
}

int main() {
    vector<int> nums = {1, 2, 2, 2, 4, 7};
    cout << lowerBound(nums, 2) << "\n";
    cout << lowerBound(nums, 3) << "\n";
    return 0;
}

Main.java

import java.util.List;

public class Main {
    static int lowerBound(List<Integer> arr, int target) {
        int lo = 0;
        int hi = arr.size(); // [lo, hi)

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr.get(mid) < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

    public static void main(String[] args) {
        List<Integer> nums = List.of(1, 2, 2, 2, 4, 7);
        System.out.println(lowerBound(nums, 2));
        System.out.println(lowerBound(nums, 3));
    }
}

main.py

def lower_bound(arr, target):
    lo, hi = 0, len(arr)  # [lo, hi)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid

    return lo

nums = [1, 2, 2, 2, 4, 7]
print(lower_bound(nums, 2))
print(lower_bound(nums, 3))
# 출력
# 1
# 4

main.rs

fn lower_bound(arr: &[i32], target: i32) -> usize {
    let mut lo: usize = 0;
    let mut hi: usize = arr.len(); // [lo, hi)

    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if arr[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    lo
}

fn main() {
    let nums = vec![1, 2, 2, 2, 4, 7];
    println!("{}", lower_bound(&nums, 2));
    println!("{}", lower_bound(&nums, 3));
}

`lower_bound` 수렴 단계 체크 포인트

arr[mid] < target이면 답은 오른쪽에 있으므로 lo = mid + 1입니다. 거짓이면 mid도 답 후보이므로 hi = mid로 줄여야 합니다. 이 규칙은 "답은 항상 [lo, hi) 안에 있다"는 불변식을 유지합니다.

평균 시간복잡도: O(log N)
최악 시간복잡도: O(log N)
공간복잡도: O(1)

경계 탐색: 첫 번째 참 위치 찾기

문제 의도: 단조 판정 함수 기반으로 경계값을 찾는 일반 이진 탐색 패턴을 학습합니다.
입력 예시: 단조 불리언 판정 시퀀스
출력 예시: 첫 true 위치 인덱스

main.cpp

#include <iostream>
using namespace std;

bool isOk(int x, int threshold) {
    return x * x >= threshold;
}

int firstTrue(int lo, int hi, int threshold) {
    // [lo, hi) 범위에서 처음 true가 되는 인덱스
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isOk(mid, threshold)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int main() {
    int threshold = 37;
    int ans = firstTrue(0, 100, threshold);
    cout << ans << " " << ans * ans << "\n";
    return 0;
}

Main.java

public class Main {
    static boolean isOk(int x, int threshold) {
        return x * x >= threshold;
    }

    static int firstTrue(int lo, int hi, int threshold) {
        // [lo, hi) 범위에서 처음 true가 되는 인덱스
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isOk(mid, threshold)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public static void main(String[] args) {
        int threshold = 37;
        int ans = firstTrue(0, 100, threshold);
        System.out.println(ans + " " + (ans * ans));
    }
}

main.py

def first_true(lo, hi, ok):
    # [lo, hi) 범위에서 처음 True가 되는 인덱스를 찾음
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

threshold = 37

def ok(x):
    return x * x >= threshold

ans = first_true(0, 100, ok)
print(ans, ans * ans)
# 출력: 7 49

main.rs

fn is_ok(x: i32, threshold: i32) -> bool {
    x * x >= threshold
}

fn first_true(mut lo: i32, mut hi: i32, threshold: i32) -> i32 {
    // [lo, hi) 범위에서 처음 true가 되는 인덱스
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if is_ok(mid, threshold) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    lo
}

fn main() {
    let threshold = 37;
    let ans = first_true(0, 100, threshold);
    println!("{} {}", ans, ans * ans);
}

`firstTrue` 판정 함수 체크 포인트

이 패턴은 배열이 없어도 적용됩니다. 정답 공간 자체를 이진 탐색하는 방식이므로 파라메트릭 서치의 기반 템플릿으로 재사용할 수 있습니다.

중요한 기준은 ok(mid)가 단조해야 한다는 점입니다. 단조성이 깨지면 절반 제거 논리가 성립하지 않습니다.

평균 시간복잡도: O(log R)
최악 시간복잡도: O(log R)
공간복잡도: O(1)

경계 탐색: `upper_bound` 변형

문제 의도: 첫 번째 > target 위치를 찾아 구간 길이 계산에 활용합니다.
입력 예시: arr=[1,2,2,2,4,7], target=2
출력 예시: 4

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int upperBound(const vector<int>& arr, int target) {
    int lo = 0;
    int hi = static_cast<int>(arr.size());

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    return lo;
}

int main() {
    vector<int> nums = {1, 2, 2, 2, 4, 7};
    cout << upperBound(nums, 2) << "\n";
    cout << upperBound(nums, 5) << "\n";
    return 0;
}

Main.java

import java.util.List;

public class Main {
    static int upperBound(List<Integer> arr, int target) {
        int lo = 0;
        int hi = arr.size();

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr.get(mid) <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

    public static void main(String[] args) {
        List<Integer> nums = List.of(1, 2, 2, 2, 4, 7);
        System.out.println(upperBound(nums, 2));
        System.out.println(upperBound(nums, 5));
    }
}

main.py

def upper_bound(arr, target):
    lo, hi = 0, len(arr)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid

    return lo

nums = [1, 2, 2, 2, 4, 7]
print(upper_bound(nums, 2))
print(upper_bound(nums, 5))
# 출력
# 4
# 5

main.rs

fn upper_bound(arr: &[i32], target: i32) -> usize {
    let mut lo: usize = 0;
    let mut hi: usize = arr.len();

    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if arr[mid] <= target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    lo
}

fn main() {
    let nums = vec![1, 2, 2, 2, 4, 7];
    println!("{}", upper_bound(&nums, 2));
    println!("{}", upper_bound(&nums, 5));
}