HardHigh Frequency35 min
Binary Search on Answer
Apply binary search to minimize/maximize a value when the predicate is monotonic.
When you can't binary search on the array directly, binary search on the ANSWER. Ask "can we achieve answer X?" and binary search on X using a feasibility check.
Binary Search on the Answer
Binary Search on Answer
Koko Eating Bananas
O(n log max)n for feasibility check × log(max) for binary search iterations.Step-by-step1 / 5
h=8. lo=1, hi=11
lo=1 (min speed), hi=max(piles)=11. Binary search for min feasible speed.