Binary Search on the Answer

We have seen binary search as the canonical divide-and-conquer search: a sorted array of $n$ keys, a target $x$, and a halving loop that finds $x$ (or proves it absent) in $O(\log n)$ comparisons. That framing is correct but narrow. The array was never the point. What binary search needs is a monotone predicate: a boolean test $p(x)$ that is false up to some boundary and true from there on. Sorted membership is just one instance, where $p(i)=(A[i]\ge x)$. Once we see binary search as locating the boundary of a monotone predicate, we can search ranges that no array ever materialises, the technique known as binary search on the answer.

Recap: binary search on a sorted array

Fix a sorted array $A[0..n)$ and a target $x$. The loop maintains an interval $[lo,hi]$ guaranteed to contain $x$ if it is present at all.

Because the interval length drops geometrically, the loop runs $O(\log n)$ times. The plain does $x$ occur? version is easy; the subtle and far more useful versions are the boundary queries.

lower_bound and upper_bound

Two queries answer almost every practical question about a sorted array:

• $\text{lower\_bound}(x)$ is the first index $i$ with $A[i]\ge x$.
• $\text{upper\_bound}(x)$ is the first index $i$ with $A[i]>x$.

Their difference $\text{upper\_bound}(x)-\text{lower\_bound}(x)$ is the count of elements equal to $x$; $\text{lower\_bound}$ itself is the insertion point that keeps $A$ sorted. Both are boundary searches over the monotone predicate $p(i)=(A[i]\ge x)$ (respectively $A[i]>x$): a sorted array makes $p$ go false, …, false, true, …, true exactly once.

The reliable template is half-open and uses lo < hi, never lo <= hi. We search for the smallest index in $[0,n]$ at which the predicate holds, treating index $n$ as a virtual past the end sentinel that is always feasible.

Two details make this correct, and getting either wrong is the classic off-by-one bug:

• The interval is half-open, $[lo,hi)$ as a search space but $hi$ inclusive as an answer. We initialize $hi\leftarrow n$, not $n-1$, because the answer can be no element is $\ge x$, i.e. index $n$. The loop's exit $lo=hi$ then names a valid boundary in $[0,n]$.
• The mid uses $\lfloor \cdot \rfloor$ and the two branches are asymmetric. When $p(mid)$ holds we set $hi\leftarrow mid$ (not $mid-1$), because $mid$ is itself a candidate boundary. When $p(mid)$ fails we set $lo\leftarrow mid+1$, because $mid$ is now known-infeasible and must be excluded. With a floored mid, $mid<hi$ always, so $hi\leftarrow mid$ strictly shrinks the interval and the loop cannot spin forever. For $\text{upper\_bound}$, change the test to $A[mid]>x$; nothing else moves.

The generalization: searching a monotone predicate

Nothing in the loop above inspected the array except through $p$. Abstract it away. Let $p:\{lo,\dots ,hi\}\to \{\text{false},\text{true}\}$ be monotone:

If $p$ is monotone and computable, we can find $x^{\star }$ by binary search over the numeric range $[lo,hi]$, with no array at all. This is binary search on the answer: we are searching the space of candidate answers, and the only thing that makes it work is that feasibility is monotone in the answer.

The cost is uniform across every application:

We pay $\log (hi-lo)$ probes, and each probe runs the feasibility check once. Replacing the array access $A[mid]\ge x$ by an arbitrary monotone test is the entire idea.

Worked examples

In each case the work is the same three steps: name the answer parameter and its range $[lo,hi]$, name the monotone predicate $p$, and write the feasibility check. The binary search loop never changes.

Koko eating bananas

Koko has piles $\text{piles}[0..n)$ and $H$ hours; at speed $s$ she clears $\lceil \text{piles}[i]/s\rceil$ hours on pile $i$. Minimize $s$ such that she finishes within $H$ hours.

• Answer parameter: the speed $s$, an integer in $[1,{\max }_i\text{piles}[i]]$.
• Predicate: $p(s)=({\sum }_i\lceil \text{piles}[i]/s\rceil \le H)$, can finish in $\le H$ hours.
• Monotonicity: a larger $s$ never increases any term $\lceil \text{piles}[i]/s\rceil$, so $p$ is monotone increasing in $s$ (false for tiny speeds, true once fast enough). Binary search the smallest feasible $s$.

Each check is $O(n)$, the range is ${\max }_i\text{piles}[i]$, so the cost is $O(n\log {\max }_i\text{piles}[i])$.

Capacity to ship / split array largest sum

These two problems are the same problem. Given an array and a count $D$ (days / parts), partition it into $D$ contiguous groups to minimize the maximum group sum. (Capacity to ship within $D$ days reads the array as package weights; Split array largest sum reads it as integers, with identical structure.)

• Answer parameter: the cap $C$ on a group's sum, in $[{\max }_i{a}_i,{\sum }_i{a}_i]$. (You cannot go below the largest single element; you never need to exceed the whole sum.)
• Predicate: $p(C)=$ the array can be split into $\le D$ contiguous groups, each with sum $\le C$.
• Feasibility check (greedy, $O(n)$): sweep left to right, accumulating into the current group; whenever adding $a_i$ would exceed $C$, close the group and start a new one at $a_i$. The number of groups this greedy uses is the minimum possible for cap $C$, so $p(C)$ holds iff that count is $\le D$.

A larger $C$ only ever merges groups, so the group count is non-increasing in $C$: $p$ is monotone, and we binary search the smallest feasible $C$. Cost: $O(n\log {\sum }_i{a}_i)$.

Integer square root

A pure-numeric instance with no array in sight: given $N\ge 0$, compute $\lfloor \sqrt{N}\rfloor$, the largest $x$ with $x^2\le N$.

• Answer parameter: $x$, in $[0,N]$ (or tighten $hi$ to $\lceil N/2\rceil +1$).
• Predicate: here the natural test $q(x)=(x^2\le N)$ is monotone the other way, namely true, …, true, false, …, so we want the last true. Search the first $x$ with $x^2>N$ via the standard $\text{lower\_bound}$ template and subtract one; or flip the comparison and keep the largest feasible form.

The check is $O(1)$, so the integer square root costs $O(\log N)$, and the same shape computes any $\lfloor N^{1/k}\rfloor$.¹

Correctness and termination

Every variant rests on one invariant, stated here for the smallest feasible half-open template ($hi$ inclusive as an answer):

Termination and correctness. With $mid=lo+\lfloor (hi-lo)/2\rfloor$ we have $lo\le mid<hi$ whenever $lo<hi$. If $p(mid)$ is true, setting $hi\leftarrow mid$ keeps $hi$ feasible and strictly decreases $hi$. If $p(mid)$ is false, setting $lo\leftarrow mid+1$ keeps everything below $lo$ infeasible and strictly increases $lo$. Either way $hi-lo$ drops by at least one and at most halves, so after $\le \lceil {\log }_2(hi-lo)\rceil$ iterations $lo=hi=x^{\star }$. $\square$

Binary search on a real interval

When the answer is a real number rather than an integer (minimize a continuous radius, a rate, a time), the boundary need not be representable exactly, so we run parametric search: the same loop on a real interval, stopping after a fixed number of iterations or once $hi-lo<\epsilon$.

Each iteration halves the interval, so $K$ iterations reach absolute error $(r-\ell )2^{-K}$; a fixed $K$ buys machine precision. There is no $\pm 1$ bookkeeping because we never need the exact integer boundary, only an $\epsilon$-close one. As always, the predicate's monotonicity is the whole game: if $p$ is monotone over $[\ell ,r]$ the loop converges to its boundary; if $p$ is not monotone, binary search is simply the wrong tool, since there may be several transitions and no guarantee which one we land on.³

Takeaways

• Binary search locates the boundary of a monotone predicate in $O(\log (\text{range}))$ probes; the sorted array is just the special case $p(i)=(A[i]\ge x)$.
• Memorise one template. The half-open while (lo < hi) form with a floored mid, $hi\leftarrow mid$ on feasible and $lo\leftarrow mid+1$ on infeasible, returning $lo$, computes $\text{lower\_bound}$ and $\text{upper\_bound}$ without off-by-one errors.
• Binary search on the answer: when feasibility is monotone in a numeric parameter, binary search the parameter and call a feasibility check at each step, for total cost $\Theta (\log (\text{range})\cdot \text{check})$.
• Recipe for each problem: name the answer range $[lo,hi]$, the monotone predicate $p$, and an efficient check. Koko (speed; sum of ceilings), ship/split (max-group cap; greedy partition in $O(n)$), integer square root ($x^2\le N$) all fit this mold.
• The correctness invariant keeps $lo$ infeasible and $hi$ feasible; floored mid plus asymmetric updates guarantee termination. Mixing the closed and half-open templates is where the classic bugs live.
• For a real-valued answer, run parametric search: a fixed iteration count or $\epsilon$ tolerance. Monotonicity of $p$ is the only precondition that matters.