Exponential search

Exponential search locates a target's possible range in a sorted sequence by probing indices $1,2,4,8,\dots$ until the target is bounded above or the sequence ends, then uses binary search inside the final bracket. If the target lies near index $k$, this takes $O(\log (k+1))$ probes under random-access and constant-comparison assumptions. For an unbounded monotone predicate, the same method brackets the first true index. It is useful when the relevant prefix is much shorter than the whole sequence or its length is not initially known. Finite sequences still require bounds checks at each probe.

To discover a positive unknown integer $m$ by comparisons, test the thresholds $2^k,2^{2k},\dots$ for fixed $k\ge 1$. If the first threshold not smaller than $m$ has index $j$, fewer than $2^{kj}$ candidates remain and binary search needs at most $kj+O(1)$ comparisons. Since $j\le {\log }_2(m)/k+1$, the total is at most $(1+1/k){\log }_{2}m+O_k(1)$. Choosing $k\ge 1/ϵ$ makes the leading constant at most $1+ϵ$; the additive constant may depend on $ϵ$.

Exponential sign bracketing finds an integer interval with opposite endpoint signs before sign-bracketing binary search. Suppose $f$ is defined on nonnegative integers, its signs can be evaluated exactly, $f(0)<0$, and $f(k)>0$ for all sufficiently large integers $k$. Test $1,2,4,\dots$. An exact zero can be returned immediately; otherwise stop at the first positive endpoint $2^t$ and retain the preceding negative endpoint, or zero when $t=0$.

Excluding the already known evaluation at zero, this takes $t+1$ endpoint tests. For $t\ge 1$, the final integer interval is $[2^{t-1},2^t]$, of width $2^{t-1}$. Repeated midpoint tests preserving opposite endpoint signs take $t-1$ further tests to reach adjacent integers, unless an exact zero is found earlier. For $t=0$, $[0,1]$ is already adjacent.

No monotonicity is needed to preserve opposite endpoint signs, though other crossings may be skipped. Adjacent opposite signs do not imply an integer root; for $f(k)=2k-1$, neither endpoint of $[0,1]$ is a root. A real-valued extension requires continuity to infer a real root by the intermediate value theorem. A machine implementation must handle integer overflow and unreliable floating-point arithmetic; mathematical termination does not ensure representable endpoints.