Binary Search on the Answer

The generalization that surprises people

Nothing in either previous lesson actually required a sorted array. What both templates needed was a monotonic predicate over a range of candidate values — and that range doesn't have to be array indices at all. It can be the space of possible answers to the problem: every integer from some minimum feasible value to some maximum. This technique — binary search on the answer — is the single most-tested generalization of binary search in interviews, precisely because it's not obviously binary search until you've learned to see it.

The recognition pattern

Three signals, together, mean "binary search on the answer":

1. The problem asks for a minimum (or maximum) value satisfying some condition — "minimum speed to finish in time," "maximum distance between placed items," "smallest capacity that works."
2. There's a feasibility check: given a candidate answer, you can determine "does this work?" in reasonable time (often O(n) or O(n log n)), even though you can't jump straight to the best one.
3. Feasibility is monotonic in the candidate value — if speed k works, every speed faster than k also works; if capacity c is enough, every larger capacity is also enough. One direction is all "no," the other is all "yes," with a single flip between them.

When all three hold, you don't need to search the problem's data structure — you binary search the range of possible answers, calling the feasibility check at each midpoint instead of comparing array values.

The template

def binary_search_on_answer(lo: int, hi: int, feasible) -> int:
    # feasible(x): True for all x >= the answer, False for all x < it
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid           # mid works — the true answer might be here or smaller
        else:
            lo = mid + 1        # mid doesn't work — answer must be larger
    return lo                   # smallest feasible value

This is exactly the boundary-search template from the previous lesson — same half-open range, same hi = mid / lo = mid + 1 split — with arr[mid] >= target replaced by a call to feasible(mid). The code is nearly identical; what changed is what mid MEANS (a candidate answer, not an array index) and what decides the branch (a feasibility computation, not an array comparison).

Bounding the search range

The one genuinely new step: you must establish lo and hi — the smallest and largest values the answer could possibly be — before searching. This usually comes straight from the problem's own constraints: "eating speed" can't be below 1 or above the largest pile (eating faster than the biggest pile finishes it in one hour, so nothing is gained past that); "minimum ship capacity that gets every package out within the allotted days" ranges from "the single heaviest package" (any less and that one package physically can't be loaded) to "the sum of every package's weight" (a capacity that large ships everything in one shipment, trivially satisfying any day limit). Reading constraints for these bounds is the same skill the Big O module built — knowing where an answer space starts and ends before you search it.

Total cost

If the feasibility check costs O(f(n)) and the answer range spans R possible values, binary search on the answer costs O(f(n) · log R) — the halving argument, with the feasibility check standing in for the O(1) comparison of ordinary binary search. The multiplication is literal: the loop still runs exactly log₂ R times (same range-halving count as every template in this module), and each of those iterations now pays a full feasibility check instead of a single array comparison — log R iterations × O(f(n)) per iteration = O(f(n) · log R). This is frequently the difference between an infeasible brute force (try every candidate answer, check each in O(f(n)): O(R · f(n))) and a fast one — R can be up to 10⁹, and log₂(10⁹) ≈ 30, so the search itself is nearly free next to the feasibility checks.

Trace the recognition pattern on Koko's actual numbers: piles = [3, 6, 7, 11], hours = 8. Feasibility at speed k: sum(ceil(pile / k) for pile in piles) <= hours. Bounds: lo = 1, hi = 12 (one past the largest pile, 11 — the half-open convention again). Iteration 1: mid = 6. Hours needed: 1+1+2+2 = 6 <= 8 — feasible, hi = 6. Iteration 2: mid = 3. Hours needed: 1+2+3+4 = 10 > 8 — infeasible, lo = 4. Iteration 3: mid = 5. Hours needed: 1+2+2+3 = 8 <= 8 — feasible, hi = 5. Iteration 4: mid = 4. Hours needed: 1+2+2+3 = 8 <= 8 — feasible, hi = 4. Now lo == hi == 4: loop ends, answer is speed 4 — four comparisons against a feasibility space of 11 candidates, and the gap widens fast as pile sizes grow.