이진 탐색 변형 문제 모음

문제 설명

정렬된 배열에서 특정 조건을 만족하는 경계를 찾는 이진 탐색 변형 패턴을 다룬다.

lower_bound: 타겟 이상의 첫 번째 인덱스
upper_bound: 타겟 초과의 첫 번째 인덱스
파라메트릭 서치: 최적화 문제를 결정 문제로 변환

해설

이진 탐색의 핵심은 탐색 공간을 절반씩 제거하는 것이다. 변형 문제에서는 lo, hi, mid 의 경계 조건이 달라지므로, 종료 조건을 명확히 정의해야 한다.

CODE

while lo < hi:
    mid = (lo + hi) // 2
    if condition(mid):
        hi = mid      # lower_bound: 조건 만족 시 hi 당김
    else:
        lo = mid + 1  # 조건 불만족 시 lo 올림

코드 풀이

Python

CODE

def lower_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def parametric_search(lo: int, hi: int, feasible) -> int:
    """최솟값 최적화 — feasible(mid) == True인 최소 mid 반환"""
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Javascript

CODE

function lowerBound(arr, target) {
  let lo = 0,
    hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function parametricSearch(lo, hi, feasible) {
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

📝 Notes

lo < hi vs lo <= hi: 종료 후 lo가 답인지 lo - 1이 답인지 구분 필요
정수 오버플로: Python은 무관, JS/Java는 (lo + hi) >> 1 권장
파라메트릭 서치: feasible 함수를 O(n)으로 구현하면 전체 O(n log n)

이진 탐색 변형 문제 모음

이진 탐색 변형 문제 모음

문제 설명

해설

코드 풀이

Python

Javascript

📝 Notes

참고 및 출처

Concepts & Tags