Binary Search on Answer
DSA · Advanced
Definition
Instead of searching an array, binary search over the range of possible answers using a yes/no check.
Solves 'minimum capacity', 'Koko eating bananas' and allocation problems.
Diagram
Flowchart
Example: Smallest k with k*k >= 50
lo, hi = 0, 50
while lo < hi:
m = (lo + hi) // 2
if m * m >= 50: hi = m
else: lo = m + 1
print(lo)Output: 8
Complexity
O(log R × cost of check)
Key points
- Check must be monotonic
- Write the feasibility function first
Interview questions
What makes it valid?
If an answer works, every larger (or smaller) answer also works.