DSA · Chapter 35 of 40
Binary Search on the Answer
Some problems have no sorted array but do have a monotonic yes/no condition: if a capacity of x works, every larger capacity also works. You can binary search over the range of possible answers instead of over the data.
Typical questions are minimum capacity to ship packages in D days, Koko eating bananas, and splitting an array into k subarrays with minimum largest sum.
The recipe
Define lo and hi as the smallest and largest plausible answers, write a feasible(x) check, then binary search for the smallest x where feasible(x) is true.
Complexity
O(n log R) where R is the range of answers and n is the cost of one feasibility check.
Example 1 (python)
def min_capacity(weights, days):
def ok(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo
print(min_capacity([1, 2, 3, 4, 5], 3))Output
6Search the answer space, not the array.
Example 2 (python)
# monotonic condition: bigger capacity is never worse
print([c for c in range(4, 9)])Output
[4, 5, 6, 7, 8]Once feasible(6) is true, 7 and 8 are also feasible.
Key points
- Works whenever the feasibility check is monotonic.
- Search over the range of answers, not the input.
- Complexity is O(n log R).
- Common in 'minimise the maximum' problems.
💡 Note: Ask yourself: 'if x works, does x+1 always work?' If yes, binary search the answer.