---
title: Binary Search on the Answer
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 4
order: 504
summary: |
  Binary search locates the boundary of a **monotone predicate** $p(x)$ in
  $O(\log(\text{range}))$ probes; sorted arrays are only one instance. We first
  establish the half-open `while (lo < hi)` template for $\textsc{lower\_bound}$
  and $\textsc{upper\_bound}$, then generalize to "binary search on the answer":
  whenever feasibility is monotone in a numeric parameter, we binary search the
  parameter itself, calling a feasibility check at each step.
topics: [Searching]
sources:
  - book: CLRS
    ref: "Ch. 2 — Binary search (Exercise 2.3-5)"
  - book: Skiena
    ref: "§4.9 — Binary Search and Related Algorithms"
  - book: Erickson
    ref: "Ch. 1 — Recursion"
practice:
  - title: 'Binary Search'
    slug: binary-search
    difficulty: Easy
  - title: 'Koko Eating Bananas'
    slug: koko-eating-bananas
    difficulty: Medium
  - title: 'Capacity To Ship Packages Within D Days'
    slug: capacity-to-ship-packages-within-d-days
    difficulty: Medium
  - title: 'Split Array Largest Sum'
    slug: split-array-largest-sum
    difficulty: Hard
  - title: 'Median of Two Sorted Arrays'
    slug: median-of-two-sorted-arrays
    difficulty: Hard
---

We have seen binary search as the canonical [divide-and-conquer](/algorithms/divide-and-conquer/mergesort) 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. What
binary search actually 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) = \parens{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 \mathinner{\ldotp\ldotp} n)$ and a target $x$. The loop maintains an
interval $[lo, hi]$ guaranteed to contain $x$ if it is present at all.

> **Invariant.** At the top of each iteration, if $x \in A$ then its index lies in
> $[lo, hi]$. Each step compares $x$ to $A[mid]$ and discards the half that
> cannot contain it, so the invariant is preserved while $hi - lo$ at least
> halves.

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:

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

Their difference $\textsc{upper\_bound}(x) - \textsc{lower\_bound}(x)$ is the count
of elements equal to $x$; $\textsc{lower\_bound}$ itself is the insertion point
that keeps $A$ sorted. Both are boundary searches over the monotone predicate
$p(i) = \parens{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.

```algorithm
caption: $\textsc{lower\_bound}(A, x)$ — first index $i$ with $A[i] \ge x$
$lo \gets 0$
$hi \gets n$ // half-open: hi is past-the-end
while $lo < hi$ do
  $mid \gets lo + \lfloor (hi - lo)/2 \rfloor$ // floor, and overflow-safe
  if $A[mid] \ge x$ then
    $hi \gets mid$ // mid may be the answer
  else
    $lo \gets mid + 1$ // mid infeasible
return $lo$ // $lo = hi$: boundary
```

::impl{algo="lower_bound"}

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 \gets 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 \gets mid$ (not $mid - 1$), because $mid$ is
  itself a candidate boundary. When $p(mid)$ fails we set $lo \gets mid + 1$,
  because $mid$ is now known-infeasible and _must_ be excluded. With a floored
  mid, $mid < hi$ always, so $hi \gets mid$ strictly shrinks the interval and the
  loop cannot spin forever. For $\textsc{upper\_bound}$, change the test to
  $A[mid] > x$; nothing else moves.

> **Intuition.** Think of $lo$ as "the frontier of proven-infeasible" and $hi$ as
> "the frontier of proven-feasible (or the sentinel)." The two markers march
> toward each other; when they meet, they pinch the boundary between the last
> `false` and the first `true`.

One caution on the mid expression. Written as $(lo + hi)/2$ in a
32-bit integer type, the sum overflows as soon as $lo + hi$ exceeds $2^{31} - 1$:
with $lo = hi = 1.6 \times 10^9$ (legal indices into a large byte array) the sum
wraps negative and the "midpoint" lands outside the interval entirely. The form
$mid \gets lo + \lfloor (hi - lo)/2 \rfloor$ computes the same value, but the
intermediate $hi - lo$ never exceeds the interval width, so it cannot overflow
while $lo \le hi$ holds. This bug sat in production binary searches for decades
because it only fires on arrays longer than a billion elements.

### The template, traced

Run $\textsc{lower\_bound}(A, 8)$ on

$$
A = \langle 2,\ 3,\ 3,\ 5,\ 8,\ 8,\ 8,\ 13 \rangle, \qquad n = 8.
$$

The first index with $A[i] \ge 8$ is $4$, and the loop finds it in three probes:

| iter. | $lo$ | $hi$ | $mid$ | $A[mid]$ | $A[mid] \ge 8$? | update |
|-------|------|------|-------|----------|-----------------|--------|
| 1 | $0$ | $8$ | $4$ | $8$ | yes | $hi \gets 4$ |
| 2 | $0$ | $4$ | $2$ | $3$ | no | $lo \gets 3$ |
| 3 | $3$ | $4$ | $3$ | $5$ | no | $lo \gets 4$ |
| exit | $4$ | $4$ | | | | return $4$ |

Iteration 3 is the critical case: the interval $[3, 4]$ holds one
untested candidate plus the feasible frontier, $mid$ floors to $lo = 3$, and the
`false` branch moves $lo$ past it. In this two-element configuration a wrong
update rule spins forever (the bug taxonomy below returns to it).

$$
% caption: $\textsc{lower\_bound}(A, 8)$ on $A=\langle 2,3,3,5,8,8,8,13\rangle$. Each row is
%          one iteration's interval $[lo, hi]$ with the probed $mid$; the dashed cell is the
%          past-the-end sentinel $n=8$. Three probes pin the boundary at index $4$
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7.5mm, inner sep=0, font=\small},
  >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\v in {0/2,1/3,2/3,3/5,4/8,5/8,6/8,7/13} {
    \node[cell] at (\i*0.9,0) {\v};
    \node[black] at (\i*0.9,0.62) {\i};
  }
  \node[cell, dashed, draw=black] at (7.2,0) {};
  \node[black] at (7.2,0.62) {8};
  % iteration 1
  \draw[black] (0,-1.3) -- (7.2,-1.3);
  \draw[black, thick] (0,-1.15) -- (0,-1.45);
  \draw[black, thick] (7.2,-1.15) -- (7.2,-1.45);
  \node[below, black] at (0,-1.45) {lo = 0};
  \node[below, black] at (7.2,-1.45) {hi = 8};
  \draw[acc, very thick] (3.6,-1.15) -- (3.6,-1.45);
  \node[above, text=acc] at (3.6,-1.18) {mid = 4};
  \node[anchor=west] at (7.9,-1.3) {A[4] = 8 $\ge$ 8: hi = 4};
  % iteration 2
  \draw[black] (0,-2.6) -- (3.6,-2.6);
  \draw[black, thick] (0,-2.45) -- (0,-2.75);
  \draw[black, thick] (3.6,-2.45) -- (3.6,-2.75);
  \node[below, black] at (0,-2.75) {lo = 0};
  \node[below, black] at (3.6,-2.75) {hi = 4};
  \draw[acc, very thick] (1.8,-2.45) -- (1.8,-2.75);
  \node[above, text=acc] at (1.8,-2.48) {mid = 2};
  \node[anchor=west] at (7.9,-2.6) {A[2] = 3 $<$ 8: lo = 3};
  % iteration 3
  \draw[black] (2.7,-3.9) -- (3.6,-3.9);
  \draw[black, thick] (3.6,-3.75) -- (3.6,-4.05);
  \node[below, black, anchor=north east] at (2.6,-4.05) {lo = 3};
  \node[below, black, anchor=north west] at (3.7,-4.05) {hi = 4};
  \draw[acc, very thick] (2.7,-3.75) -- (2.7,-4.05);
  \node[above, text=acc] at (2.7,-3.78) {mid = 3};
  \node[anchor=west] at (7.9,-3.9) {A[3] = 5 $<$ 8: lo = 4};
  % exit
  \draw[acc, very thick] (3.6,-4.85) -- (3.6,-5.15);
  \node[below, text=acc] at (3.6,-5.15) {lo = hi: return 4};
\end{tikzpicture}
$$

The same array answers the counting question. $\textsc{upper\_bound}(A, 8)$
tests $A[mid] > 8$ instead: it probes $A[4] = 8$ (no, $lo \gets 5$), then
$A[6] = 8$ (no, $lo \gets 7$), then $A[7] = 13$ (yes, $hi \gets 7$), and returns
$7$. The number of $8$s is $7 - 4 = 3$, computed without ever scanning the run
of equal keys: counting duplicates stays $O(\log n)$ even when the run has
length $\Theta(n)$.

## 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 \{\texttt{false}, \texttt{true}\}$ be
**monotone**:

> **Definition (monotone predicate).** $p$ is monotone if $p(x) \Rightarrow p(y)$
> for all $y \ge x$. Equivalently its truth pattern is
> $$\underbrace{F\,F\,\cdots\,F}_{\text{below boundary}}\ \underbrace{T\,T\,\cdots\,T}_{\ge \text{boundary}},$$
> with a single transition. The **boundary** is the smallest $x^\star$ with
> $p(x^\star)$ true.

The $F \cdots F\, T \cdots T$ pattern in the definition is forced, not assumed.
Monotonicity says the true-set $\{x : p(x)\}$ is **upward closed**: if it
contains $x$ it contains everything above $x$. An upward-closed subset of
$\{lo, \dots, hi\}$ is a suffix, so it is either empty, or exactly
$\{x^\star, \dots, hi\}$ for $x^\star = \min\{x : p(x)\}$. There is one
transition or none, and the "none" case is why the template carries an
always-feasible sentinel at $hi$: it guarantees the true-set is nonempty, and
"no real answer exists" comes back encoded as the sentinel itself.

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. Monotonicity
is what makes the search [sound and complete](/algorithms/foundations/what-is-an-algorithm)
for the threshold: the single $F \to T$ transition means the boundary we return is
the true $x^\star$ and no other transition can be mistaken for it.

$$
% caption: A monotone predicate flips false→true exactly once; binary search finds that
%          boundary, the smallest feasible answer $x^\star$
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=0, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (c0) at (0,0) {$F$};
  \node[cell] (c1) at (0.8,0) {$F$};
  \node[cell] (c2) at (1.6,0) {$F$};
  \node[cell] (c3) at (2.4,0) {$F$};
  \node[cell, draw=acc, very thick] (c4) at (3.2,0) {$T$};
  \node[cell] (c5) at (4.0,0) {$T$};
  \node[cell] (c6) at (4.8,0) {$T$};
  \node[cell] (c7) at (5.6,0) {$T$};
  \draw[acc, thick] (3.2,0.9) -- (3.2,0.5);
  \node[text=acc, font=\footnotesize, align=center] at (3.2,1.25)
    {smallest feasible answer};
\end{tikzpicture}
$$

The cost is uniform across every application:

$$
\Theta\parens{\log(\text{range}) \cdot \text{cost of one } p\text{-check}}.
$$

We pay $\lceil \log_2(hi - lo) \rceil$ probes, because each iteration replaces
the interval width $w = hi - lo$ by at most $\lceil w/2 \rceil$, so after $k$
probes the width is at most $w / 2^k$, and the loop stops when it reaches $0$.
The logarithm is what makes the technique scale: a range of $10^9$ costs
$30$ probes, and a range of $10^{18}$ costs $60$. Sixty evaluations of a
feasibility check settle a question over an answer space no machine could
enumerate. Replacing the array access $A[mid] \ge x$ by an arbitrary monotone
test is the entire idea.

::impl{algo="binary_search_answer"}

$$
% caption: Each probe tests $p(mid)$ and discards the infeasible half —
%          $O(\log(\text{range}))$ probes
\begin{tikzpicture}[
  >=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % row 1
  \draw[thick] (0,0) -- (8,0);
  \node[below, font=\footnotesize] at (0,-0.1) {lo};
  \node[below, font=\footnotesize] at (8,-0.1) {hi};
  \node[above, text=acc, font=\footnotesize] at (4,0.1) {mid};
  \draw[acc, thick] (4,0.18) -- (4,-0.18);
  \draw[->, red!75!black, thick] (4.2,0.45) -- node[above, font=\footnotesize, text=red!75!black]{p(mid) true: drop righ\/t half} (7.8,0.45);
  % row 2
  \draw[thick] (0,-1.8) -- (4,-1.8);
  \node[below, font=\footnotesize] at (0,-1.9) {lo};
  \node[below, font=\footnotesize] at (4,-1.9) {hi};
  \node[above, text=acc, font=\footnotesize] at (2,-1.7) {mid};
  \draw[acc, thick] (2,-1.62) -- (2,-1.98);
  \draw[->, red!75!black, thick] (1.8,-1.35) -- node[above, font=\footnotesize, text=red!75!black]{p(mid) false: drop left half} (0.2,-1.35);
  % row 3
  \draw[thick] (2,-3.0) -- (4,-3.0);
  \node[below, font=\footnotesize] at (2,-3.1) {lo};
  \node[below, font=\footnotesize] at (4,-3.1) {hi};
  \node[right, font=\footnotesize, text=acc] at (4.2,-3.0) {converges to lo = hi};
\end{tikzpicture}
$$

## 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 $\textit{piles}[0 \mathinner{\ldotp\ldotp} n)$ and $H$ hours; at speed $s$ she clears
$\lceil \textit{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 \textit{piles}[i]]$.
- **Predicate:** $p(s) = \parens{\sum_i \lceil \textit{piles}[i]/s \rceil \le H}$,
  "can finish in $\le H$ hours."
- **Monotonicity:** a larger $s$ never increases any term $\lceil \textit{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 \textit{piles}[i]$, so the cost is
$O(n \log \max_i \textit{piles}[i])$.

::impl{algo="koko_eating_bananas"}

$$
% caption: Koko feasibility over speeds for $\textit{piles}=\langle 3,6,7,11\rangle$,
%          $H=8$. The predicate
%          $p(s)=\parens{\sum_i\lceil \textit{piles}[i]/s\rceil\le 8}$ flips $F{\to}T$
%          once; binary search returns the boundary $s^\star=4$
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\footnotesize, black, anchor=east] at (0.45,0.75) {speed s};
  \node[font=\footnotesize, black, anchor=east] at (0.45,0.3) {hours};
  \node[font=\footnotesize, black, anchor=east] at (0.45,-0.3) {p(s)};
  \foreach \s/\h in {1/27,2/15,3/10,4/8,5/8,6/6} {
    \node[font=\footnotesize] at (\s*1.1,0.75) {\s};
    \node[font=\footnotesize] at (\s*1.1,0.3) {\h};
  }
  \foreach \s/\b in {1/F,2/F,3/F} {
    \node[draw, minimum size=8mm, inner sep=0] at (\s*1.1,-0.3) {$\b$};
  }
  \foreach \s/\b in {5/T,6/T} {
    \node[draw, minimum size=8mm, inner sep=0] at (\s*1.1,-0.3) {$\b$};
  }
  \node[draw=acc, very thick, minimum size=8mm, inner sep=0] at (4.4,-0.3) {$T$};
  \draw[acc, thick] (4.4,-1.0) -- (4.4,-0.7);
  \node[text=acc, font=\footnotesize] at (4.4,-1.35) {smallest feasible s = 4};
\end{tikzpicture}
$$

The table above is what the predicate _looks like_; the search never builds it.
Run the loop on this instance. The range is $[1, 11]$, and $hi = 11$ is a
legitimate always-feasible sentinel: at speed $\max_i \textit{piles}[i]$ every
pile takes exactly one hour, so the total is $n = 4 \le 8 = H$. Four probes
suffice ($\lceil \log_2 10 \rceil = 4$), and each one evaluates the actual sum
of ceilings:

| probe | $[lo, hi]$ | $mid$ | $\sum_i \lceil \textit{piles}[i]/mid \rceil$ | $\le 8$? | update |
|-------|------------|-------|----------------------------------------------|----------|--------|
| 1 | $[1, 11]$ | $6$ | $1 + 1 + 2 + 2 = 6$ | yes | $hi \gets 6$ |
| 2 | $[1, 6]$ | $3$ | $1 + 2 + 3 + 4 = 10$ | no | $lo \gets 4$ |
| 3 | $[4, 6]$ | $5$ | $1 + 2 + 2 + 3 = 8$ | yes | $hi \gets 5$ |
| 4 | $[4, 5]$ | $4$ | $1 + 2 + 2 + 3 = 8$ | yes | $hi \gets 4$ |
| exit | $[4, 4]$ | | | | return $4$ |

Probes 3 and 4 happen to compute the same total, $8$ hours at both $s = 5$ and
$s = 4$; the check uses the total only through the comparison, and the
search still needs probe 4 to learn that $4$ is feasible while $3$ is not. Out
of eleven candidate speeds, only four were ever examined.

$$
% caption: The search over speeds for $\textit{piles}=\langle 3,6,7,11\rangle$, $H=8$: four
%          probes, numbered in order and labelled with the hours each check computed, narrow
%          $[1,11]$ to the boundary $s^\star=4$. The shaded band is the feasible suffix
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \fill[acc!8] (2.975,-0.22) rectangle (9.7,0.22);
  \draw[thick] (0.5,0) -- (9.7,0);
  \foreach \s in {1,2,3,5,6,7,8,9,10,11} {
    \draw (\s*0.85,0.1) -- (\s*0.85,-0.1);
    \node[below, black] at (\s*0.85,-0.12) {\s};
  }
  \draw[acc, very thick] (3.4,0.24) -- (3.4,-0.24);
  \node[below, text=acc] at (3.4,-0.12) {4};
  % probes, in search order
  \draw[acc] (5.1,0.3) -- (5.1,0.65);
  \node[above, text=acc] at (5.1,0.65) {1) 6 h: T};
  \draw[acc] (2.55,0.3) -- (2.55,0.65);
  \node[above, text=acc] at (2.55,0.65) {2) 10 h: F};
  \draw[acc] (4.25,0.3) -- (4.25,1.35);
  \node[above, text=acc] at (4.25,1.35) {3) 8 h: T};
  \draw[acc] (3.4,0.3) -- (3.4,2.05);
  \node[above, text=acc] at (3.4,2.05) {4) 8 h: T};
  % region labels
  \node[black] at (1.7,-0.85) {infeasible};
  \node[text=acc] at (6.5,-0.85) {feasible};
\end{tikzpicture}
$$

### 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$.

> **Lemma.** The left-to-right greedy uses the minimum number of groups for a
> given cap $C$. _Proof sketch._ The first group can extend no further than the
> greedy takes it without exceeding $C$; an exchange argument pushes any optimal
> partition's first cut rightward to match the greedy's, then induct on the
> suffix. $\qed$

$$
% caption: Feasibility check for cap $C=18$ on $\langle 7,2,5,10,8\rangle$ with $D=2$: the
%          greedy sweep cuts whenever the next element would push a group past $C$, using
%          $2$ groups (sums $14\le18$, $18\le18$). Since $2\le D$, $p(18)$ holds
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\v in {0/7,1/2,2/5,3/10,4/8} {
    \node[draw, minimum size=8mm, inner sep=1pt] (a\i) at (\i*0.95,0) {$\v$};
  }
  \draw[acc, very thick] (-0.45,-0.5) rectangle (2.35,0.5);
  \draw[acc, very thick] (2.45,-0.5) rectangle (4.25,0.5);
  \node[font=\footnotesize, acc, align=center] at (0.95,-1.15) {group 1\\sum = 14};
  \node[font=\footnotesize, acc, align=center] at (3.35,-1.15) {group 2\\sum = 18};
  \node[font=\footnotesize] at (1.9,1.0) {cut: 14 + 10 $>$ 18};
  \draw[acc, thick] (2.4,0.75) -- (2.4,-0.75);
\end{tikzpicture}
$$

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)$.

::impl{algo="split_array_largest_sum"}

On $\langle 7, 2, 5, 10, 8 \rangle$ with $D = 2$ the range is
$[\max, \text{sum}] = [10, 32]$, and the search runs the greedy sweep four
times:

| probe | $[lo, hi]$ | $C = mid$ | greedy groups | count | $\le 2$? | update |
|-------|------------|-----------|---------------|-------|----------|--------|
| 1 | $[10, 32]$ | $21$ | $\langle 7,2,5 \rangle\ \langle 10,8 \rangle$ | $2$ | yes | $hi \gets 21$ |
| 2 | $[10, 21]$ | $15$ | $\langle 7,2,5 \rangle\ \langle 10 \rangle\ \langle 8 \rangle$ | $3$ | no | $lo \gets 16$ |
| 3 | $[16, 21]$ | $18$ | $\langle 7,2,5 \rangle\ \langle 10,8 \rangle$ | $2$ | yes | $hi \gets 18$ |
| 4 | $[16, 18]$ | $17$ | $\langle 7,2,5 \rangle\ \langle 10 \rangle\ \langle 8 \rangle$ | $3$ | no | $lo \gets 18$ |
| exit | $[18, 18]$ | | | | | return $18$ |

Probes 2 and 4 fail for the same structural reason: once $C < 18$, the packages
$10$ and $8$ can no longer share a group, and the greedy is forced to three.
The returned optimum $18 = 10 + 8$ is itself a sum of a contiguous run,
necessarily: $p$ is a step function of $C$ whose value can only change
at caps equal to some contiguous-run sum, so the smallest feasible cap always
lands on one. The binary search does not exploit this; it simply cannot
return anything else.

### 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 $\textsc{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$.[^erickson-search]

::impl{algo="integer_root"}

$$
% caption: Reversed monotonicity: $q(x)=(x^2\le N)$ runs $T\cdots T\,F\cdots F$, so the
%          answer is the LAST true, not the first. For $N=10$ the boundary sits at
%          $x^\star=3$ ($9\le10<16$)
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=0, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \x/\b in {0/T,1/T,2/T,3/T} {
    \node[cell] (c\x) at (\x*0.8,0) {$\b$};
    \node[font=\footnotesize, black] at (\x*0.8,0.6) {$\x$};
  }
  \node[cell, draw=acc, very thick] at (2.4,0) {};
  \foreach \x/\b in {4/F,5/F,6/F,7/F} {
    \node[cell] at (\x*0.8,0) {$\b$};
    \node[font=\footnotesize, black] at (\x*0.8,0.6) {$\x$};
  }
  \draw[acc, thick] (2.4,-0.9) -- (2.4,-0.5);
  \node[text=acc, font=\footnotesize, align=center] at (2.4,-1.25)
    {last feasible x = 3};
\end{tikzpicture}
$$

Traced for $N = 10$ with the flip: search the first $x$ with $x^2 > 10$ over
$[0, 7]$ (any $hi$ with $hi^2 > N$ works as the sentinel; $7^2 = 49 > 10$).
Probe $mid = 3$: $9 > 10$ fails, $lo \gets 4$. Probe $mid = 5$: $25 > 10$
holds, $hi \gets 5$. Probe $mid = 4$: $16 > 10$ holds, $hi \gets 4$. The loop
exits at $lo = hi = 4$, and $\lfloor \sqrt{10} \rfloor = 4 - 1 = 3$.

### When monotonicity fails

The precondition is easy to violate with an innocent-looking change of
predicate. Ask Koko's question with equality instead of inequality:
$q(s) = \parens{\text{hours}(s) = 8}$, "she finishes in _exactly_ $H$ hours."
On $\textit{piles} = \langle 3, 6, 7, 11 \rangle$ the hour totals for
$s = 1, \dots, 11$ are $27, 15, 10, 8, 8, 6, 5, 5, 5, 5, 4$, so $q$ reads

$$
F\ F\ F\ T\ T\ F\ F\ F\ F\ F\ F,
$$

two transitions. Feed this to the smallest-feasible template:
the first probe is $mid = 6$, $q(6)$ is `false`, and the template concludes the
boundary lies to the _right_, setting $lo \gets 7$. Both true cells are gone.
Every later probe is `false` too, so the loop drifts up to the sentinel and
returns $11$, a speed that does not even satisfy $q$. Nothing inside the loop
misbehaved; the precondition was false, so the invariant "everything below $lo$
is infeasible" broke at the very first update.

$$
% caption: An equality predicate is not monotone: $q(s)=\parens{\text{hours}(s)=8}$ on Koko's
%          instance is true only at $s\in\{4,5\}$, so it has two transitions. The first probe
%          $q(6)=F$ makes the template discard $s\le 6$, losing both true cells; the search
%          drifts to the sentinel $11$, which is not a solution at all
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7mm, inner sep=0, font=\small},
  >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \s/\b in {1/F,2/F,3/F,6/F,7/F,8/F,9/F,10/F} {
    \node[cell] at (\s*0.85,0) {$\b$};
    \node[black] at (\s*0.85,0.58) {\s};
  }
  \foreach \s in {4,5} {
    \node[cell, draw=acc, very thick] at (\s*0.85,0) {$T$};
    \node[black] at (\s*0.85,0.58) {\s};
  }
  \node[cell] at (9.35,0) {$F$};
  \node[black] at (9.35,0.58) {11};
  % two transitions
  \draw[acc, thick] (2.975,0.9) -- (2.975,1.15);
  \draw[acc, thick] (4.675,0.9) -- (4.675,1.15);
  \node[text=acc] at (3.825,1.4) {two transitions};
  % probe and discard
  \draw[red!75!black, thick] (5.1,-0.5) -- (5.1,-0.85);
  \node[below, text=red!75!black] at (5.1,-0.85) {prob\/e: q(6) = F};
  \draw[->, red!75!black, thick] (5.45,-1.7) --
    node[below, text=red!75!black]{discards s = 1..6, both T cells lost} (0.5,-1.7);
  \node[draw=red!75!black, dashed, minimum size=8.4mm, inner sep=0] at (9.35,0) {};
  \node[below, text=red!75!black] at (9.35,-0.5) {returned};
\end{tikzpicture}
$$

The repair is standard: search a monotone _relaxation_ and test afterwards.
Here, find the smallest $s$ with $\text{hours}(s) \le 8$ (the original monotone
predicate, giving $s = 4$), then check whether $\text{hours}(4) = 8$ happens to
hold. More generally, before trusting any answer-space search, write the
one-line monotonicity argument ("increasing the parameter only relaxes the
constraint, so a feasible answer stays feasible") and confirm the sentinel $hi$
is feasible by construction. If either fails, the loop still terminates and
still returns _something_; it just returns garbage.

## Correctness and termination

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

> **Invariant.** At the top of each iteration, $lo$ is infeasible-or-just-below
> the boundary and $hi$ is feasible (or the always-feasible sentinel): every index
> $< lo$ has $p = $ `false`, and $p(hi) = $ `true`. The boundary $x^\star$ always
> lies in $[lo, hi]$.

> **Proof (termination & 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 \gets mid$ keeps $hi$ feasible and strictly decreases $hi$. If $p(mid)$ is
> `false`, setting $lo \gets 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$. $\qed$

> **Remark (Where off-by-one bugs hide).** There are two viable templates, and mixing them
> is the classic error:
>
> 1. **Half-open `while (lo < hi)`** with $hi$ a valid answer, $hi \gets mid$ /
>    $lo \gets mid + 1$, return $lo$. (Used above. The mid _must_ floor.)
> 2. **Closed `while (lo <= hi)`** with $hi = n - 1$, $hi \gets mid - 1$ /
>    $lo \gets mid + 1$, tracking the best answer seen.
>
> The fatal combinations are: `lo <= hi` with $hi \gets mid$ (infinite loop,
> since the interval never shrinks when $lo = mid$), and `lo < hi` with $hi \gets mid - 1$
> (skips a candidate, returning one short). Pick one template and never improvise
> the updates. A defining symptom of the infinite-loop bug is that it only fires
> on the two-element interval, where $mid$ floors to $lo$.[^clrs-binsearch]

To see the loop bug fire, suppose we want the _last_ `true` (the
integer-square-root shape) and, improvising, keep the floored $mid$ with the
updates $lo \gets mid$ on `true` and $hi \gets mid - 1$ on `false`. On the
two-element interval $lo = 4$, $hi = 5$ with $p(4)$ true: $mid = 4 + \lfloor
(5-4)/2 \rfloor = 4$, the `true` branch assigns $lo \gets 4$, and the state is
exactly what it was. The loop runs forever, and it does so only when the search
has already narrowed to two candidates, which is why the bug survives casual
testing: small hand-checked examples that happen to exit earlier look fine.

The correct "last true" mirror uses the **ceiling** midpoint:

```algorithm
caption: largest $x$ with $p(x)$ — the mirrored template needs a ceiling mid
$lo \gets \ell;\ hi \gets r$ // invariant: $p(lo)$ true, everything above $hi$ false
while $lo < hi$ do
  $mid \gets lo + \lceil (hi - lo)/2 \rceil$ // ceiling: $mid > lo$ always
  if $p(mid)$ then
    $lo \gets mid$ // mid feasible, may be the answer
  else
    $hi \gets mid - 1$ // mid known-infeasible
return $lo$
```

Now $mid > lo$ whenever $lo < hi$, so both branches strictly shrink the
interval; the roles of the floor and ceiling are symmetric to the roles of
$hi \gets mid$ and $lo \gets mid$. The rule of thumb: whichever side the update
_keeps_ ($hi \gets mid$ or $lo \gets mid$), round $mid$ **away** from that side.
Floor pairs with $hi \gets mid$; ceiling pairs with $lo \gets mid$. This form
returns the largest feasible value directly, which is what the integer square
root wanted before we flipped it into a first-`false` search.

## 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 < \varepsilon$.

```algorithm
caption: real-valued binary search — first $x$ with $p(x)$ within $\varepsilon$
$lo \gets \ell;\ hi \gets r$
repeat $K$ times: // $K=100$ $\Rightarrow$ error $\le(r-\ell)2^{-100}$
  $mid \gets (lo + hi)/2$
  if $p(mid)$ then $hi \gets mid$ else $lo \gets mid$
return $hi$
```

Each iteration halves the interval, so $K$ iterations reach absolute error
$(r-\ell)\,2^{-K}$; solving for the iteration count that reaches a tolerance
$\varepsilon$ gives

$$
K = \left\lceil \log_2 \frac{r - \ell}{\varepsilon} \right\rceil.
$$

The numbers stay small even for extravagant demands: an interval of width
$10^9$ pushed down to $\varepsilon = 10^{-6}$ needs
$\lceil \log_2 10^{15} \rceil = 50$ iterations. There is no $\pm 1$ bookkeeping
because we never need the exact integer boundary, only an $\varepsilon$-close
one.

Preferring a fixed $K$ over the loop condition `while (hi - lo > eps)` matters
for correctness. A double carries $52$ significand bits, so once the interval is a
few units in the last place wide, $(lo + hi)/2$ rounds to $lo$ or $hi$ and the
interval stops shrinking; if
$\varepsilon$ is below that granularity, the `eps`-condition never becomes
false and the loop hangs. A fixed $K$ (around $100$ for doubles, comfortably
past machine precision) is immune by construction. As always, **the predicate's
monotonicity is the real precondition**: 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.[^skiena-binsearch]

::impl{algo="parametric_search"}

## Parametric search, bisection, and decision vs. optimization

"Binary search on the answer" is the discrete, hand-rolled special case of a
broad optimization paradigm. When the feasibility check is itself a shortest-path
or flow computation, the technique is **parametric search** (Megiddo, _Applying
Parallel Computation Algorithms in the Design of Serial Algorithms_, JACM 1983),
which replaces the numeric probe with a simulation of the check run on the
unknown optimum, and is the classical route to problems like the minimum-ratio
cycle and the $k$-th smallest distance. The everyday version — pick a value,
run a Boolean feasibility test, halve the range — is what this lesson
does, and it is worth recognizing that the two are the same idea at different
levels of sophistication.

The continuous analogue, **bisection on a monotone real predicate**, is a
root-finding method: to solve $f(x) = 0$ for monotone $f$, binary search the
sign of $f$. Bisection converges linearly (one bit per step), which is why
numerical libraries pair it with faster-but-fragile methods — Brent's method
(Brent, _Algorithms for Minimization Without Derivatives_, 1973) falls back to
bisection whenever the superlinear step would leave the bracketing interval, so
it keeps bisection's guaranteed convergence while usually running faster. The
"binary search on a real parameter until the interval is small enough" pattern
in this lesson is bisection with an explicit tolerance, and the same caution
applies: it needs a genuine sign change (a genuine monotone predicate) bracketed
at the endpoints, or it converges to nothing meaningful.

Finally, the monotone-predicate framing connects binary search to **decision vs.
optimization**. Many optimization problems are solved by reducing them to a
sequence of decision ("is a solution of quality $\ge k$ feasible?") problems and
binary searching $k$; the reduction is efficient precisely when the decision
version is polynomial and feasibility is monotone in $k$. That is the same move
that turns an NP optimization problem into its NP decision counterpart, and in
the tractable case it is this lesson's technique verbatim.

## 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 \gets mid$ on feasible and $lo \gets mid + 1$ on infeasible, returning
  $lo$, computes $\textsc{lower\_bound}$ and $\textsc{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, and the infinite-loop
  variants all fire on the two-element interval. Rounding rule: floor pairs
  with $hi \gets mid$, ceiling with $lo \gets mid$.
- Use binary search on the answer when **checking is easy but solving is
  hard**: evaluating "is cap $C$ enough?" is a linear greedy sweep, while
  computing the optimal $C$ directly is not. The search converts a verifier
  into an optimizer at a $\log$ factor.
- **Verify monotonicity before trusting the output.** Equality-style predicates
  have two transitions and send the search to garbage without any visible
  failure; search the monotone relaxation ($\le$ instead of $=$) and test the
  boundary afterwards. Confirm the sentinel $hi$ is feasible by construction.
- For a real-valued answer, run **parametric search**: a fixed iteration count
  $K = \lceil \log_2((r-\ell)/\varepsilon) \rceil$ rather than an `eps` loop
  condition, which can hang at floating-point granularity. Monotonicity of $p$
  is the only precondition that matters.

[^clrs-binsearch]: **CLRS**, Ch. 2 — Binary search (Exercise 2.3-5): the $O(\log n)$ sorted-array search and its boundary (insertion-point) variants.
[^skiena-binsearch]: **Skiena**, §4.9 — Binary Search and Related Algorithms: searching a monotone predicate over a numeric range ("binary search on the answer") and one-sided/parametric variants.
[^erickson-search]: **Erickson**, Ch. 1 — Recursion: binary search as recursive boundary-finding, including pure-numeric instances such as integer roots.