Binary Search on the Answer
Guess an answer, check feasibility in linear time, and binary search over the monotonic feasible range.
Binary SearchO(n log(range))New13 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
minimise the maximum
maximise the minimum
smallest speed / capacity / days that works
The template
Get this into muscle memory, then adapt the condition per problem.
let lo = minAns, hi = maxAns;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
feasible(mid) ? (hi = mid) : (lo = mid + 1);
}
return lo; Watch Binary Search on the AnswerIf you are stuck
The generic hint ladder for this pattern, in order.
- 1The array is unsorted, so what exactly is monotonic here?
- 2If a capacity of X works, every capacity above X also works.
- 3Write the feasibility check first, then wrap binary search around it.
Drill it
Every problem in the bank that uses this pattern.
0 / 13 solved