Search on Answer

The Pattern

Standard binary search works on sorted arrays. Search on answer flips the script: instead of searching for a value inside the data, you search for the answer directly within a numeric range. The key insight is that many optimization problems are easier to check than to compute — given a candidate answer, can you tell in O(n) whether it works? If yes, and the decision function is monotonic (once a value works, all larger/smaller values also work), then binary search finds the optimal answer in O(log range × feasibility cost).

For example: "What is the minimum ship capacity to deliver all packages within D days?" You don't know the capacity, but you can test any capacity in O(n) by simulating the shipping. The feasible capacities form a contiguous range [minCap, ∞), so binary search pinpoints the minimum.

When to Use

• Minimize maximum: split an array into k subarrays to minimize the largest sum, ship packages within D days, divide jobs among workers.
• Maximize minimum: place k cows in stalls to maximize the minimum distance, allocate resources fairly.
• Bounded search space: the answer lies within a known numeric range [lo, hi] that you can iterate over.
• Easy feasibility check: you can verify in O(n) or O(n log n) whether a candidate answer works.
• Monotonic decision: if candidate x works, then x+1 also works (or x-1 also works).
• Non-standard input: the answer isn't an element of the array; it's a derived bound.

Template

The template always consists of three parts: define the search bounds [lo, hi], write a feasible(candidate) → bool function, and binary search over the range. The two variants differ in mid calculation and pointer movement:

The ceiling division in the maximize-min variant prevents infinite loops when lo and hi are adjacent.

Problems