Recap — Binary Search on the Answer

# Binary Search on the Answer Standard binary search is "find X in sorted array". The interview-worthy version is "find the smallest answer that satisfies a monotonic predicate" — applicable far beyond sorted arrays. ## Standard binary search ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo = target." ```python def lower_bound(arr, target): lo, hi = 0, len(arr) while lo target." ```python def upper_bound(arr, target): lo, hi = 0, len(arr) while lo < hi: mid = (lo + hi) // 2 if arr[mid] <= target: lo = mid + 1 else: hi = mid return lo ``` `bisect.bisect_right` does this. ## The unified template For any binary search: ```python def search(predicate, lo, hi): while lo < hi: mid = (lo + hi) // 2 if predicate(mid): hi = mid else: lo = mid + 1 return lo # first value where predicate is True ``` `predicate` is a monotonic function: False for small values, True for large (or vice versa). ## Binary search on the ANSWER The interview-worthy pattern. Instead of searching in an array, search in the SOLUTION SPACE. When applicable: - Answer is bounded by lo and hi (you know minimum and maximum possible answer). - You can check "is X a valid answer?" in some bounded time. - The "is X valid" predicate is monotonic in X. ### Example: Minimum eating speed (Koko Eating Bananas) "Pile of bananas; K hours to eat all. Find minimum speed." ```python def min_eating_speed(piles, h): def can_finish(speed): return sum((p + speed - 1) // speed for p in piles) <= h lo, hi = 1, max(piles) while lo < hi: mid = (lo + hi) // 2 if can_finish(mid): hi = mid else: lo = mid + 1 return lo ``` Search space: speeds 1 to max(piles). Predicate: "can finish in h hours at this speed?". Monotonic: if speed S works, S+1 also works. ### Example: Split array largest sum "Split N-element array into K non-empty subarrays; minimize the maximum subarray sum." ```python def split_array(nums, k): def can_split(max_sum): groups = 1 current = 0 for x in nums: if current + x > max_sum: groups += 1 current = x if groups > k: return False else: current += x return True lo, hi = max(nums), sum(nums) while lo < hi: mid = (lo + hi) // 2 if can_split(mid): hi = mid else: lo = mid + 1 return lo ``` Search the answer (max sum). Predicate: "can I split with this max sum?". ### Pattern: Recognize "binary search on answer" Signals: - "Minimum X such that...", "Maximum X such that..." - Predicate "is X valid?" is checkable in O(N) or O(N log N). - Predicate is monotonic in X. If you can answer "is THIS THE answer?" faster than finding the optimum, you can binary search. ## Common binary search pitfalls ### Off-by-one with mid ```python mid = (lo + hi) // 2 # rounds DOWN; for lo + 1 = hi, mid = lo mid = (lo + hi + 1) // 2 # rounds UP; useful when hi = mid causes infinite loop ``` When you set `lo = mid` instead of `lo = mid + 1`, you need to round up. ### Integer overflow In Python: not an issue. In C++/Java: use `lo + (hi - lo) // 2` to avoid overflow. ### Inclusive vs exclusive bounds Decide upfront: `lo` is inclusive or exclusive? Stick to one style. The lo < hi (exclusive hi) style is cleaner for most patterns; lo <= hi for "find exact match". ### Infinite loops If your loop condition is `lo < hi` and neither bound changes on some path → infinite loop. Trace through a 2-element case. ## Common binary-search mistakes 1. **Forgetting monotonicity.** If predicate isn't monotonic, binary search doesn't apply. 2. **Searching for an exact value when bounds are needed.** Standard binary search returns -1 on miss; bisect returns insertion point. 3. **Wrong bounds for "search on answer".** Make sure lo and hi cover the actual answer. 4. **Mixing two styles in one function.** Pick `lo <= hi` or `lo < hi`; don't mix. ## Takeaway Standard binary search: log N to find in sorted array. Lower/upper bound: bisect_left, bisect_right. Binary search on the answer: search the SOLUTION SPACE; use a predicate to check va