# 이진 탐색 변형 문제 모음 ## 문제 설명 정렬된 배열에서 특정 조건을 만족하는 경계를 찾는 이진 탐색 변형 패턴을 다룬다. - **lower_bound**: 타겟 이상의 첫 번째 인덱스 - **upper_bound**: 타겟 초과의 첫 번째 인덱스 - **파라메트릭 서치**: 최적화 문제를 결정 문제로 변환 ## 해설 이진 탐색의 핵심은 **탐색 공간을 절반씩 제거**하는 것이다. 변형 문제에서는 `lo`, `hi`, `mid` 의 경계 조건이 달라지므로, 종료 조건을 명확히 정의해야 한다. ``` while lo < hi: mid = (lo + hi) // 2 if condition(mid): hi = mid # lower_bound: 조건 만족 시 hi 당김 else: lo = mid + 1 # 조건 불만족 시 lo 올림 ``` ## 코드 풀이 ### Python ```python 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 ```javascript 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) --- ## 참고 및 출처 - [programmers Coding Test](https://school.programmers.co.kr/learn/challenges) - [LeetCode](https://leetcode.com/)