Answer-Space Binary Search
Treat a continuous answer range as a search space to solve problems like minimum-time-to-complete-jobs and capacity-to-ship-packages.
Binary Search on Answer Space
Most people know binary search for finding a value in a sorted array. But binary search is even more powerful when applied to the space of possible answers. Instead of searching an array, you search a numeric range — for example, 'what is the minimum number of days to ship all packages?' — and use a check function to decide whether a candidate answer is feasible.
This technique converts many optimisation problems from O(n²) or worse to O(n log(max_answer)).
The Answer-Space Template
The template has three components. First, define the search range [lo, hi] that brackets all valid answers. Second, write a feasibility check can_achieve(mid) that returns True if the mid value is achievable. Third, binary search over [lo, hi]: if can_achieve(mid), move toward a smaller (or larger) answer; otherwise move in the other direction.
The key property: the feasibility function must be monotone — once an answer is feasible, all values beyond it are also feasible (or all below are infeasible).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return result