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. 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) = (A [i] \geq 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 $[l o, 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:

$lower_bound (x)$ is the first index $i$ with $A [i] \geq x$ .
$upper_bound (x)$ is the first index $i$ with $A [i] > x$ .

Their difference $upper_bound (x) - lower_bound (x)$ is the count of elements equal to $x$ ; $lower_bound$ itself is the insertion point that keeps $A$ sorted. Both are boundary searches over the monotone predicate $p (i) = (A [i] \geq 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:

\textsc{lower\_bound}(A, x)

— first index

i

with

A[i] \ge x

1
$lo \gets 0$
2
$hi \gets n$
half-open: hi is past-the-end
3
while $lo < hi$ do
4
$mid \gets lo + \lfloor (hi - lo)/2 \rfloor$
floor, and overflow-safe
5
if $A[mid] \ge x$ then
6
$hi \gets mid$
mid may be the answer
7
else
8
$lo \gets mid + 1$
mid infeasible
9
return $lo$
$lo = hi$ : boundary

lower_bound.pypython

from typing import Sequence, TypeVar

from comparable import Comparable

Key = TypeVar("Key", bound=Comparable)

def lower_bound(sorted_values: Sequence[Key], target: Key) -> int:
  """
    The first index `i` with `sorted_values[i] >= target`.\n
    This is the insertion point that keeps the array sorted; it equals\n
    len(sorted_values) when every element is strictly less than target.\n
  """
  low: int = 0
  high: int = len(sorted_values)  # half-open: high is past-the-end.

  # narrow to the first index whose value reaches target.
  while low < high:
    middle: int = low + (high - low) // 2
    if sorted_values[middle] >= target:
      high = middle  # middle may itself be the boundary.
    else:
      low = middle + 1  # middle is known infeasible; exclude it.

  return low

def upper_bound(sorted_values: Sequence[Key], target: Key) -> int:
  """
    The first index `i` with `sorted_values[i] > target`.\n
    Differs from lower_bound only in the strictness of the comparison;\n
    `upper_bound - lower_bound` counts the elements equal to target.\n
  """
  low: int = 0
  high: int = len(sorted_values)

  # narrow to the first index whose value strictly exceeds target.
  while low < high:
    middle: int = low + (high - low) // 2
    if sorted_values[middle] > target:
      high = middle
    else:
      low = middle + 1

  return low

def count_equal(sorted_values: Sequence[Key], target: Key) -> int:
  """
    How many entries equal `target`, as the width of the equal run.\n
  """
  return upper_bound(sorted_values, target) - lower_bound(sorted_values, target)

def contains(sorted_values: Sequence[Key], target: Key) -> bool:
  """
    Whether `target` occurs in the sorted array.\n
  """
  index: int = lower_bound(sorted_values, target)
  return index < len(sorted_values) and sorted_values[index] == target

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

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

The interval is half-open, $[l o, 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 $\geq x$ , i.e. index $n$ . The loop's exit $l o = hi$ then names a valid boundary in $[0, n]$ .
The mid uses $⌊ \cdot ⌋$ and the two branches are asymmetric. When $p (mi d)$ holds we set $hi \leftarrow mi d$ (not $mi d - 1$ ), because $mi d$ is itself a candidate boundary. When $p (mi d)$ fails we set $l o \leftarrow mi d + 1$ , because $mi d$ is now known-infeasible and must be excluded. With a floored mid, $mi d < hi$ always, so $hi \leftarrow mi d$ strictly shrinks the interval and the loop cannot spin forever. For $upper_bound$ , change the test to $A [mi d] > x$ ; nothing else moves.

One caution on the mid expression. Written as $(l o + hi) /2$ in a 32-bit integer type, the sum overflows as soon as $l o + hi$ exceeds $2^{31} - 1$ : with $l o = hi = 1.6 \times 1 0^{9}$ (legal indices into a large byte array) the sum wraps negative and the midpoint lands outside the interval entirely. The form $mi d \leftarrow l o + ⌊(hi - l o) /2 ⌋$ computes the same value, but the intermediate $hi - l o$ never exceeds the interval width, so it cannot overflow while $l o \leq 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 $lower_bound (A, 8)$ on

A = ⟨ 2, 3, 3, 5, 8, 8, 8, 13 ⟩, n = 8.

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

iter.	$l o$	$hi$	$mi d$	$A [mi d]$	$A [mi d] \geq 8$ ?	update
1	$0$	$8$	$4$	$8$	yes	$hi \leftarrow 4$
2	$0$	$4$	$2$	$3$	no	$l o \leftarrow 3$
3	$3$	$4$	$3$	$5$	no	$l o \leftarrow 4$
exit	$4$	$4$				return $4$

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

lower_bound (A, 8)

A = ⟨ 2, 3, 3, 5, 8, 8, 8, 13 ⟩

. Each row is one iteration's interval

[l o, hi]

with the probed

mi d

; the dashed cell is the past-the-end sentinel

n = 8

. Three probes pin the boundary at index

4

The same array answers the counting question. $upper_bound (A, 8)$ tests $A [mi d] > 8$ instead: it probes $A [4] = 8$ (no, $l o \leftarrow 5$ ), then $A [6] = 8$ (no, $l o \leftarrow 7$ ), then $A [7] = 13$ (yes, $hi \leftarrow 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 $Θ (n)$ .

The generalization: searching a monotone predicate

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

The $F \dots F T \dots 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 ${l o, \dots, hi}$ is a suffix, so it is either empty, or exactly ${x^{⋆}, \dots, hi}$ for $x^{⋆} = 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^{⋆}$ by binary search over the numeric range $[l o, 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 for the threshold: the single $F \to T$ transition means the boundary we return is the true $x^{⋆}$ and no other transition can be mistaken for it.

A monotone predicate flips false→true exactly once; binary search finds that boundary, the smallest feasible answer

x^{⋆}

The cost is uniform across every application:

Θ (log (range) \cdot cost of one p -check) .

We pay $⌈ log_{2} (hi - l o)⌉$ probes, because each iteration replaces the interval width $w = hi - l o$ by at most $⌈ w /2 ⌉$ , 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 $1 0^{9}$ costs $30$ probes, and a range of $1 0^{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 [mi d] \geq x$ by an arbitrary monotone test is the entire idea.

binary_search_answer.pypython

from typing import Callable

def first_true(low: int, high: int, predicate: Callable[[int], bool]) -> int:
  """
    The smallest integer `x` in [low, high] with `predicate(x)` true,\n
    for a predicate whose truth pattern is F..F T..T (monotone increasing).\n
    `high` is treated as an always-feasible sentinel: it is returned when no\n
    smaller value satisfies the predicate. Requires low <= high.\n
  """
  # shrink toward the first feasible value; floored mid keeps it moving.
  while low < high:
    middle: int = low + (high - low) // 2
    if predicate(middle):
      high = middle  # feasible; middle may be the boundary.
    else:
      low = middle + 1  # infeasible; exclude middle.

  return low

def last_true(low: int, high: int, predicate: Callable[[int], bool]) -> int:
  """
    The largest integer `x` in [low, high] with `predicate(x)` true,\n
    for a predicate whose truth pattern is T..T F..F (monotone decreasing).\n
    `low` is treated as an always-feasible sentinel. Requires low <= high.\n
  """
  # shrink toward the last feasible value; ceiled mid never sticks at `low`.
  while low < high:
    middle: int = low + (high - low + 1) // 2
    if predicate(middle):
      low = middle  # feasible; middle may be the boundary.
    else:
      high = middle - 1  # infeasible; exclude middle.

  return low

Each probe tests

p (mi d)

and discards the infeasible half —

O (log (range))

probes

Worked examples

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

Koko eating bananas

Koko has piles $piles [0 .. n)$ and $H$ hours; at speed $s$ she clears $⌈ piles [i] / s ⌉$ hours on pile $i$ . Minimize $s$ such that she finishes within $H$ hours.

Answer parameter: the speed $s$ , an integer in $[1, max_{i} piles [i]]$ .
Predicate: $p (s) = (\sum_{i} ⌈ piles [i] / s ⌉ \leq H)$ , can finish in $\leq H$ hours.
Monotonicity: a larger $s$ never increases any term $⌈ piles [i] / s ⌉$ , 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} piles [i]$ , so the cost is $O (n log max_{i} piles [i])$ .

koko_eating_bananas.pypython

from math import ceil
from typing import Sequence

from binary_search_answer import first_true

def hours_needed(piles: Sequence[int], speed: int) -> int:
  """
    Total hours to clear every pile at the given eating `speed`.\n
  """
  return sum(ceil(pile / speed) for pile in piles)

def minimum_eating_speed(piles: Sequence[int], hours: int) -> int:
  """
    The least integer speed at which Koko finishes all `piles` within\n
    `hours`. Assumes hours >= len(piles) (otherwise no speed suffices).\n
    Returns 0 when there are no piles.\n
  """
  if not piles:
    return 0

  def can_finish(speed: int) -> bool:
    return hours_needed(piles, speed) <= hours

  fastest: int = max(piles)  # speed >= max pile always finishes in n hours.
  return first_true(1, fastest, can_finish)

Koko feasibility over speeds for

piles = ⟨ 3, 6, 7, 11 ⟩

H = 8

. The predicate

p (s) = (\sum_{i} ⌈ piles [i] / s ⌉ \leq 8)

flips

F \to T

once; binary search returns the boundary

s^{⋆} = 4

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} piles [i]$ every pile takes exactly one hour, so the total is $n = 4 \leq 8 = H$ . Four probes suffice ( $⌈ log_{2} 10 ⌉ = 4$ ), and each one evaluates the actual sum of ceilings:

probe	$[l o, hi]$	$mi d$	$\sum_{i} ⌈ piles [i] / mi d ⌉$	$\leq 8$ ?	update
1	$[1, 11]$	$6$	$1 + 1 + 2 + 2 = 6$	yes	$hi \leftarrow 6$
2	$[1, 6]$	$3$	$1 + 2 + 3 + 4 = 10$	no	$l o \leftarrow 4$
3	$[4, 6]$	$5$	$1 + 2 + 2 + 3 = 8$	yes	$hi \leftarrow 5$
4	$[4, 5]$	$4$	$1 + 2 + 2 + 3 = 8$	yes	$hi \leftarrow 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.

The search over speeds for

piles = ⟨ 3, 6, 7, 11 ⟩

H = 8

: four probes, numbered in order and labelled with the hours each check computed, narrow

[1, 11]

to the boundary

s^{⋆} = 4

. The shaded band is the feasible suffix

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 $\leq D$ contiguous groups, each with sum $\leq 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 $\leq D$ .

Feasibility check for cap

C = 18

⟨ 7, 2, 5, 10, 8 ⟩

with

D = 2

: the greedy sweep cuts whenever the next element would push a group past

C

, using

2

groups (sums

14 \leq 18

18 \leq 18

). Since

2 \leq D

p (18)

holds

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

split_array_largest_sum.pypython

from typing import Sequence

from binary_search_answer import first_true

def groups_needed(values: Sequence[int], cap: int) -> int:
  """
    The minimum number of contiguous groups whose sums each stay <= `cap`,\n
    found by greedily extending the current group until the next element\n
    would overflow it. Assumes every element is <= cap.\n
  """
  groups: int = 1
  current_sum: int = 0
  for value in values:
    if current_sum + value > cap:  # would overflow; close and start anew.
      groups += 1
      current_sum = value
    else:
      current_sum += value
  return groups

def split_array_largest_sum(values: Sequence[int], parts: int) -> int:
  """
    The smallest possible value of the largest group sum when `values` is\n
    split into at most `parts` contiguous groups. Returns 0 for an empty\n
    array. Assumes values are non-negative and 1 <= parts.\n
  """
  if not values:
    return 0

  def fits(cap: int) -> bool:
    return groups_needed(values, cap) <= parts

  smallest_cap: int = max(values)  # cannot go below the largest element.
  largest_cap: int = sum(values)  # one group never needs more than this.
  return first_true(smallest_cap, largest_cap, fits)

On $⟨ 7, 2, 5, 10, 8 ⟩$ with $D = 2$ the range is $[max, sum] = [10, 32]$ , and the search runs the greedy sweep four times:

probe	$[l o, hi]$	$C = mi d$	greedy groups	count	$\leq 2$ ?	update
1	$[10, 32]$	$21$	$⟨ 7, 2, 5 ⟩ ⟨ 10, 8 ⟩$	$2$	yes	$hi \leftarrow 21$
2	$[10, 21]$	$15$	$⟨ 7, 2, 5 ⟩ ⟨ 10 ⟩ ⟨ 8 ⟩$	$3$	no	$l o \leftarrow 16$
3	$[16, 21]$	$18$	$⟨ 7, 2, 5 ⟩ ⟨ 10, 8 ⟩$	$2$	yes	$hi \leftarrow 18$
4	$[16, 18]$	$17$	$⟨ 7, 2, 5 ⟩ ⟨ 10 ⟩ ⟨ 8 ⟩$	$3$	no	$l o \leftarrow 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 \geq 0$ , compute $⌊ N ⌋$ , the largest $x$ with $x^{2} \leq N$ .

Answer parameter: $x$ , in $[0, N]$ (or tighten $hi$ to $⌈ N /2 ⌉ + 1$ ).
Predicate: here the natural test $q (x) = (x^{2} \leq 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 $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 $⌊ N^{1/ k} ⌋$ .¹

integer_root.pypython

from binary_search_answer import last_true

def integer_sqrt(number: int) -> int:
  """
    The floor of the square root of `number` >= 0: the largest x with\n
    x*x <= number.\n
  """
  if number < 0:
    raise ValueError("integer_sqrt is undefined for negative input")
  if number < 2:
    return number  # 0 and 1 are their own floor-roots.

  # any x > number/2 + 1 already squares past number, so cap the search there.
  highest: int = number // 2 + 1
  return last_true(0, highest, lambda candidate: candidate * candidate <= number)

def integer_root(number: int, degree: int) -> int:
  """
    The floor of the `degree`-th root of `number` >= 0: the largest x with\n
    x ** degree <= number. Requires degree >= 1.\n
  """
  if number < 0:
    raise ValueError("integer_root is undefined for negative input")
  if degree < 1:
    raise ValueError("degree must be at least 1")
  if number < 2 or degree == 1:
    return number

  highest: int = number  # x ** degree grows fast, but N is always a safe cap.
  return last_true(0, highest, lambda candidate: candidate**degree <= number)

Reversed monotonicity:

q (x) = (x^{2} \leq N)

runs

T \dots T F \dots F

, so the answer is the LAST true, not the first. For

N = 10

the boundary sits at

x^{⋆} = 3

(

9 \leq 10 < 16

)

Traced for $N = 10$ with the flip: search the first $x$ with $x^{2} > 10$ over $[0, 7]$ (any $hi$ with $h i^{2} > N$ works as the sentinel; $7^{2} = 49 > 10$ ). Probe $mi d = 3$ : $9 > 10$ fails, $l o \leftarrow 4$ . Probe $mi d = 5$ : $25 > 10$ holds, $hi \leftarrow 5$ . Probe $mi d = 4$ : $16 > 10$ holds, $hi \leftarrow 4$ . The loop exits at $l o = hi = 4$ , and $⌊ 10 ⌋ = 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) = (hours (s) = 8)$ , she finishes in exactly $H$ hours. On $piles = ⟨ 3, 6, 7, 11 ⟩$ 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 $mi d = 6$ , $q (6)$ is false, and the template concludes the boundary lies to the right, setting $l o \leftarrow 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 $l o$ is infeasible broke at the very first update.

An equality predicate is not monotone:

q (s) = (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 \leq 6

, losing both true cells; the search drifts to the sentinel

11

, which is not a solution at all

The repair is standard: search a monotone relaxation and test afterwards. Here, find the smallest $s$ with $hours (s) \leq 8$ (the original monotone predicate, giving $s = 4$ ), then check whether $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):

To see the loop bug fire, suppose we want the last true (the integer-square-root shape) and, improvising, keep the floored $mi d$ with the updates $l o \leftarrow mi d$ on true and $hi \leftarrow mi d - 1$ on false. On the two-element interval $l o = 4$ , $hi = 5$ with $p (4)$ true: $mi d = 4 + ⌊(5 - 4) /2 ⌋ = 4$ , the true branch assigns $l o \leftarrow 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:largest

x

with

p(x)

— the mirrored template needs a ceiling mid

1
$lo \gets \ell;\ hi \gets r$
invariant: $p(lo)$ true, everything above $hi$ false
2
while $lo < hi$ do
3
$mid \gets lo + \lceil (hi - lo)/2 \rceil$
ceiling: $mid > lo$ always
4
if $p(mid)$ then
5
$lo \gets mid$
mid feasible, may be the answer
6
else
7
$hi \gets mid - 1$
mid known-infeasible
8
return $lo$

Now $mi d > l o$ whenever $l o < hi$ , so both branches strictly shrink the interval; the roles of the floor and ceiling are symmetric to the roles of $hi \leftarrow mi d$ and $l o \leftarrow mi d$ . The rule of thumb: whichever side the update keeps ( $hi \leftarrow mi d$ or $l o \leftarrow mi d$ ), round $mi d$ away from that side. Floor pairs with $hi \leftarrow mi d$ ; ceiling pairs with $l o \leftarrow mi d$ . 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 - l o < ε$ .

Algorithm:real-valued binary search — first

x

with

p(x)

within

\varepsilon

1
$lo \gets \ell;\ hi \gets r$
2
repeat $K$ times:
$K=100$ $\Rightarrow$ error $\le(r-\ell)2^{-100}$
3
$mid \gets (lo + hi)/2$
4
if $p(mid)$ then $hi \gets mid$ else $lo \gets mid$
5
return $hi$

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

K = ⌈ log_{2} \frac{r - ℓ}{ε} ⌉ .

The numbers stay small even for extravagant demands: an interval of width $1 0^{9}$ pushed down to $ε = 1 0^{- 6}$ needs $⌈ log_{2} 1 0^{15} ⌉ = 50$ iterations. There is no $\pm 1$ bookkeeping because we never need the exact integer boundary, only an $ε$ -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, $(l o + hi) /2$ rounds to $l o$ or $hi$ and the interval stops shrinking; if $ε$ 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 $[ℓ, 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.³

parametric_search.pypython

from typing import Callable

def first_feasible_real(
  left: float,
  right: float,
  predicate: Callable[[float], bool],
  iterations: int = 100,
) -> float:
  """
    The boundary of a monotone-increasing real predicate on [left, right]:\n
    the least x with `predicate(x)` true, to within (right - left) * 2 ** -K.\n
    Assumes predicate(left) is false-or-just-below and predicate(right) is\n
    true. Requires left <= right and iterations >= 0.\n
  """
  low: float = left
  high: float = right

  # halve the interval a fixed number of times; high tracks the feasible side.
  for _ in range(iterations):
    middle: float = (low + high) / 2.0
    if predicate(middle):
      high = middle  # feasible; the boundary is at or below middle.
    else:
      low = middle  # infeasible; the boundary is above middle.

  return high

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 $\geq 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 (range))$ probes; the sorted array is just the special case $p (i) = (A [i] \geq x)$ .
Memorise one template. The half-open while (lo < hi) form with a floored mid, $hi \leftarrow mi d$ on feasible and $l o \leftarrow mi d + 1$ on infeasible, returning $l o$ , computes $lower_bound$ and $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 $Θ (log (range) \cdot check)$ .
Recipe for each problem: name the answer range $[l o, 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} \leq N$ ) all fit this mold.
The correctness invariant keeps $l o$ 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 \leftarrow mi d$ , ceiling with $l o \leftarrow mi d$ .
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 ( $\leq$ 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 = ⌈ log_{2} ((r - ℓ) / ε)⌉$ rather than an eps loop condition, which can hang at floating-point granularity. Monotonicity of $p$ is the only precondition that matters.

Erickson, Ch. 1 — Recursion: binary search as recursive boundary-finding, including pure-numeric instances such as integer roots. ↩
CLRS, Ch. 2 — Binary search (Exercise 2.3-5): the $O (log n)$ sorted-array search and its boundary (insertion-point) variants. ↩
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. ↩

Recap: binary search on a sorted array

lower_bound and upper_bound

The template, traced

The generalization: searching a monotone predicate

Worked examples

Koko eating bananas

Capacity to ship / split array largest sum

Integer square root

When monotonicity fails

Correctness and termination

Binary search on a real interval

Parametric search, bisection, and decision vs. optimization

Takeaways

Footnotes