Binary Search Beyond Sorted Arrays: Searching on the Answer

Binary search works on any monotonic answer space, not just sorted arrays. Treat the unknown answer as a numeric range and repeatedly test a midpoint with a yes/no predicate.

Why binary search on the answer works

The core of binary search is a predicate P(x) that is false for all values below a threshold and true for all values at or above it (or the opposite). This monotonic behavior guarantees that the set of true values forms a contiguous suffix (or prefix) of the integer line. When such a predicate exists, the exact point where the transition occurs can be found in O(log(range)) steps, exactly the same complexity as searching a sorted list. The technique appears in classic interview problems: minimum ship capacity to deliver packages within D days, smallest divisor that yields at most K subarrays, or the banana‑eating‑by‑monkey problem where the answer is the maximum feasible eating speed.

Choosing correct search bounds

Bounds must enclose the true answer. For capacity‑type problems the lower bound is often the maximum single element (you cannot ship a package larger than the ship), and the upper bound is the sum of all elements (a single trip can always carry everything). For divisor problems the lower bound may be 1 and the upper bound the maximum possible divisor, often the largest element or the total sum. Picking bounds that are too tight can miss the solution; picking bounds that are too loose only adds a few extra iterations because the logarithmic factor is small.

When the answer is an integer, use inclusive bounds [lo, hi]. Initialize lo to the smallest feasible value, hi to the largest feasible value. The loop condition is while lo < hi. Inside the loop compute mid = lo + (hi - lo) / 2 (integer division). Evaluate P(mid). If P(mid) is true, the answer lies at mid or lower, so set hi = mid. If false, the answer is higher, so set lo = mid + 1. The loop terminates with lo == hi, the minimal value satisfying P.

Off‑by‑one pitfalls

1. Mid calculation – using (lo + hi) / 2 can overflow in languages with fixed‑size integers. The safe formula lo + (hi - lo) / 2 avoids this.
2. Updating bounds – forgetting the +1 when moving lo forward leaves the loop stuck on the same mid. Conversely, setting hi = mid - 1 when P(mid) is true discards the true answer if the predicate is true at the exact threshold.
3. Inclusive vs exclusive – mixing an exclusive upper bound (while lo < hi) with an inclusive update (hi = mid) works, but switching to while lo <= hi requires different updates (hi = mid - 1). Stick to one pattern throughout the implementation.
4. Non‑integer answer spaces – for real‑valued answers use a tolerance epsilon and stop when hi - lo < epsilon. The update rules stay the same, but the termination condition changes

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.