Binary Search on the Answer — The Most Underrated Trick

Binary search on the answer searches not through an array, but through the possible values of the answer itself. If the answer falls in range [lo, hi] and you can write a feasibility function that checks "is answer X achievable?", you can binary search on X. This converts O(n²) or O(n³) brute force into O(n log n) or O(n²) solutions.

Look for the phrases "minimum X such that..." or "maximum X such that..." with a large numeric range in the constraints (suggesting the answer itself is what you search). The feasibility check must be monotonic: if X is feasible, then X+1 is also feasible (or vice versa). Classic examples: Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum.

Set lo = minimum possible answer, hi = maximum possible answer. While lo < hi: mid = lo + (hi - lo) // 2. If feasible(mid): hi = mid (looking for leftmost feasible). Else: lo = mid + 1. Return lo. The feasibility function is where the problem logic lives — it typically runs in O(n) or O(n log n), making the total O(n log(hi-lo)).

Must-know binary search problems: Binary Search (LC 704), Find Minimum in Rotated Sorted Array (LC 153), Search in Rotated Sorted Array (LC 33), Koko Eating Bananas (LC 875), Capacity to Ship Packages in D Days (LC 1011), Split Array Largest Sum (LC 410), and Median of Two Sorted Arrays (LC 4 — Hard). The rotated array variants appear frequently at Amazon and Google.