Pattern #05
Binary Search on Answer
EssentialBinary search the answer value itself; check if a candidate is feasible in linear time.
When to use
You need min/max of some value X such that a greedy or scan can verify whether X is achievable. classic for capacity, speed, and split problems.
Recognition cues
- Minimize the maximum / maximize the minimum
- Koko eating bananas, ship packages, split array largest sum
- Feasibility check is O(n) and monotonic in the guessed answer
Common pitfalls
- Wrong search bounds (lo/hi too tight or too wide)
- Feasibility that is not actually monotonic
- Integer division when computing mid or rates
90-second recognition drill
Which pattern fits best?
- Minimize the maximum / maximize the minimum
- Koko eating bananas, ship packages, split array largest sum
- Feasibility check is O(n) and monotonic in the guessed answer
Interactive
Mental model
A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.
feasible(x) is monotonic
Search the answer domain, not array indices. Example: min feasible speed.
How to think about it
You are not searching an array index. You search the answer domain [lo, hi]. For a guess mid, run feasible(mid). Because feasibility is monotonic, binary search finds the first true (min) or last true (max).
Recipe
- Prove monotonicity: if
Xworks, larger (or smaller) also works. - Set
lo/hito tight valid bounds. - Implement a correct
feasible. - Binary search for first true (min) or last true (max).
Complexity baseline
O(n log R) where R is the size of the answer range.
Template
Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.
/** Binary search on answer: first mid where feasible(mid) is true. */
export function binarySearchOnAnswer(
lo: number,
hi: number,
feasible: (mid: number) => boolean,
): number {
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
/** Binary search on answer: first mid where feasible(mid) is true. */
export function binarySearchOnAnswer(
lo: number,
hi: number,
feasible: (mid: number) => boolean,
): number {
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
- 1#410 Split Array Largest SumGuidehard
- 2#774 Minimize Max Distance to Gas StationGuidehard
- 3#875 Koko Eating BananasGuidemedium
- 4#1011 Capacity To Ship Packages Within D DaysGuidemedium
- 5#1283 Find the Smallest Divisor Given a ThresholdGuidemedium
- 6#1482 Minimum Number of Days to Make m BouquetsGuidemedium