Exponential Search

Exponential search (also known as galloping search, doubling search, or Struzik search) is a comparison-based algorithm within computation and algorithms for locating a target key x inside a sorted array or an unbounded sorted stream. Introduced by Jon Louis Bentley and Andrew Chi-Chih Yao in 1976 as part of an investigation into nearly optimal unbounded searching, the algorithm operates in two distinct phases: an outward finger-probing phase that tests array indices at exponentially increasing powers of two (1, 2, 4, 8, …, 2^k) until discovering an upper bound that exceeds or equals the target, followed by a classical divide-and-conquer binary search restricted to the bracketed interval [2^k−1, min(2^k, n − 1)].

Whereas standard binary search over an n-element sorted array always requires ⌊log₂ n⌋ + 1 comparisons regardless of where the target resides, exponential search adapts to the target's rank i (its 1-based distance from the start of the array or from a previously maintained finger position), completing in at most 2⌊log₂ i⌋ + 2 key comparisons—an asymptotic complexity of O(log i). This position-sensitive bound makes exponential search foundational for unbounded search problems where the total array length n is unknown in advance, for adaptive merging in sorting algorithms such as Timsort, and for intersecting skewed posting lists in information-retrieval search engines alongside indexed structures like the B-tree and van Emde Boas tree.

Searching Without an Upper Bound

In the classical bounded search problem, an algorithm is given a sorted array A[0 .. n − 1] together with the explicit size parameter n, allowing binary search to probe the midpoint ⌊(n − 1)/2⌋ on its very first step. In the unbounded search problem formulated by Bentley and Yao (1976), the algorithm is instead presented with an infinite (or arbitrarily long) monotonically increasing sequence A[1] < A[2] < A[3] < … and a target value x, without knowing the total length of the sequence or any initial upper bound on the index i where A[i] ≥ x. Equivalently, every probe evaluates an oracle function f(j) that returns whether A[j] < x, A[j] = x, or A[j] > x, and the task is to identify the smallest index i satisfying A[i] ≥ x using as few oracle evaluations as possible as a function of the unknown answer i.

A naive linear scan tests indices 1, 2, 3, …, i sequentially and requires i comparisons, which degrades to Θ(n) when x lies deep inside a finite table. Conversely, jumping outward by a fixed stride s requires ⌈i / s⌉ + ⌈log₂ s⌉ comparisons, which still scales linearly with i for any fixed constant s. Exponential search resolves this tension by multiplicative rather than additive stride growth, balancing the cost of overshooting the target index i against the cost of binary searching the resulting bracket.

Prefix Coding Connection and Kraft's Inequality

Bentley and Yao observed a formal equivalence between any deterministic unbounded search algorithm and a prefix-free binary code over the positive integers. Because each comparison prior to locating the upper bound produces a binary outcome (whether A[j] < x or A[j] ≥ x), a deterministic strategy that resolves the target index i in C(i) comparisons defines a binary decision tree in which the path to leaf i is a self-delimiting codeword of length C(i) bits. By Kraft's inequality, the comparison counts C(1), C(2), C(3), … of any valid unbounded search algorithm must satisfy:

Consequently, no unbounded search algorithm can achieve C(i) ≤ log₂ i for all i, because the harmonic series ∑_i=1..∞ (1 / i) diverges. Any valid comparison bound must include at least one additional iterated logarithmic overhead term so that the Kraft sum converges.

Phase 1 (Galloping Bound Discovery) and Phase 2 (Binary Search)

Given a 0-indexed sorted array A[0 .. n − 1] and a search key x, exponential search executes as follows:

1. Boundary check: If n = 0, return not found. Compare x against A[0]; if A[0] = x, return index 0, and if x < A[0], return not found (insertion point 0).
2. Phase 1 — Galloping (exponential doubling): Initialize a bound variable b ← 1. While b < n and A[b] < x, double the bound via a single bit shift: b ← 2b.
3. Early match check: If b < n and A[b] = x, return b directly.
4. Phase 2 — Binary search on the bracketed subinterval: At termination of Phase 1, the previous probe at index low = ⌊b / 2⌋ + 1 satisfied A[⌊b / 2⌋] < x, while the current bound high = min(b − 1, n − 1) bounds the upper end of the candidate range. Execute standard binary search on the contiguous subarray A[low .. high].

Suppose the target key x lies at 1-based rank i (so 2^k−1 < i ≤ 2^k for k = ⌈log₂ i⌉). Phase 1 performs k + 1 = ⌊log₂ i⌋ + 2 comparisons to verify that A[2⁰], A[2¹], …, A[2^k−1] are smaller than x and that A[2^k] ≥ x. Phase 2 then binary searches a bracket of width at most 2^k − 2^k−1 − 1 = 2^k−1 − 1 elements, requiring at most k = ⌊log₂ i⌋ comparisons. Summing both phases establishes the worst-case comparison bound:

Unary-Binary Search (B₁) vs. Binary-of-Unary-of-Binary Search (B₂)

In Bentley and Yao's taxonomy, standard exponential search is designated Algorithm B₁ because it encodes the binary length k = ⌊log₂ i⌋ + 1 in unary (performing k linear probes at 2⁰, 2¹, …, 2^k−1) before resolving the remaining k − 1 mantissa bits of i via binary search. Because the unary scan spends ⌊log₂ i⌋ + 1 comparisons just to determine k, the leading coefficient on log₂ i is 2 rather than 1.

To reduce the leading coefficient on log₂ i from 2 to 1, Bentley and Yao introduced Algorithm B₂ (corresponding to Peter Elias's γ and δ universal codes in information theory). Instead of probing every power of two 2⁰, 2¹, 2², …, Algorithm B₂ discovers the exponent k itself by applying exponential search to the sequence of exponents—probing indices at doubly exponential positions 2²⁰, 2²¹, 2²², …, 2^2m (i.e., indices 2, 4, 16, 256, 65536, …) until A[2^2m] ≥ x. It then uses binary search on the exponent range [2^m−1, 2^m] to pinpoint k = ⌊log₂ i⌋ in 2⌊log₂ k⌋ + 2 comparisons, and finally performs a standard binary search of k comparisons within [2^k−1, 2^k]. The total comparison count of B₂ is:

The Ultimate Algorithm (B_U) and the Iterated Logarithm

Extending this recursion across all levels yields Bentley and Yao's Ultimate Algorithm B_U (equivalent to the Elias ω universal code), which recursively invokes B_U to find the binary length of the binary length of i down to base size 1. Algorithm B_U completes in:

comparisons, where log i is the iterated logarithm. By Kraft's inequality and a theorem of Luther J. Woodall (1976), this bound is within an additive O(log i) term of the information-theoretic lower bound for any prefix-free comparison tree. In practical in-memory computing, however, n ≤ 2⁶⁴ so ⌊log₂ i⌋ ≤ 64, and the sequential cache prefetching and branch-prediction regularity of simple power-of-two doubling make B₁ faster in wall-clock execution than B₂ or B_U unless each comparison invokes an expensive external-memory I/O operation or a high-latency network RPC.

Inverted-Index Posting List Intersection (SvS and Barbay–Kenyon)

In full-text search engines and relational database query processors, each term t maps to a sorted posting list of document identifiers. Answering a conjunctive multi-word query requires computing the set intersection of k sorted posting lists of widely varying lengths n₁ ≤ n₂ ≤ … ≤ n_k. In the SvS (Small-vs-Small) algorithm studied by Hwang and Lin (1972) and the adaptive intersection algorithm of Jérémy Barbay and Claire Kenyon (2002), advancing through the shortest list L₁ and using galloping (exponential) search starting from the previous match finger in each longer list L_j intersects a list of size m with a list of size n (m ≤ n) in:

comparisons, matching the information-theoretic lower bound log₂ C(n, m) = Θ(m log(n / m)). Moreover, starting each exponential search from the last examined index (a finger search) preserves spatial locality inside CPU cache lines, outperforming both full-array binary search and pointer-heavy balanced trees such as the splay tree or y-fast trie on compressed integer arrays.

Galloping Mode in Timsort

Tim Peters's adaptive hybrid merge sort (Timsort, 2002)—the standard sorting algorithm in Python, Java, Android, and V8—merges adjacent sorted runs A and B one element at a time while monitoring how many consecutive times the winning element comes from the same run. Once a single run wins MIN-GALLOP (default 7) times in a row, Timsort switches from one-by-one linear merging into galloping mode: it executes an exponential search in the winning run to find the entire contiguous prefix of elements smaller than the current head of the losing run, and copies that entire block in a single bulk memory move. If the runs are already partitioned or contain long clustered streaks, galloping reduces the number of comparisons for merging runs of lengths m and n from m + n − 1 down to O(m log(n / m)).

When is exponential search faster than standard binary search on a finite array of known size n?

Exponential search outperforms standard binary search whenever the target element (or insertion point) is expected to lie near the beginning of the array—or near a maintained finger index f from a prior query—so that the distance i satisfies 2⌊log₂ i⌋ + 2 < ⌊log₂ n⌋ + 1, which holds whenever i < √(n / 2). When queries are uniformly distributed across the entire array [0 .. n − 1] with no prior finger, standard binary search (or interpolation search on uniform numerical keys) uses roughly half as many comparisons.

Why does exponential search multiply the probe offset by 2 instead of a larger base b > 2?

Multiplying the step size by a general base b > 1 reaches a target at distance i in ⌈log_b i⌉ outward probes, leaving a bracket of size (b − 1) · b^{⌈log_b i⌉ − 1} ≈ (b − 1)i for the binary search phase. The total comparison count is approximately (1 / log₂ b + 1) log₂ i + log₂(b − 1). Choosing b = 2 aligns every step with a single bit shift, keeps the bracket width at most i, and avoids integer multiplication overhead, though bases b = 4 (quadrupling search) are occasionally used in SIMD-vectorized posting list intersection to match 4-wide register lanes.

How does exponential finger search avoid running off the end of a finite array?

In a finite array of length n with a current finger at index f, the galloping loop tests offsets f + (2^k − 1) while checking f + (2^k − 1) < n at each step. If the next doubled index would exceed n − 1, the upper bound is clamped to high = n − 1 and Phase 2 binary searches the final suffix [f + 2^k−1, n − 1] directly.

1. Bentley, J. L., & Yao, A. C.-C. (1976). "An almost optimal algorithm for unbounded searching." Information Processing Letters, 5(3), 82–87. https://doi.org/10.1016/0020-0190(76)90071-590071-5)
2. Elias, P. (1975). "Universal codeword sets and representations of the integers." IEEE Transactions on Information Theory, 21(2), 194–203. https://doi.org/10.1109/TIT.1975.1055349
3. Hwang, F. K., & Lin, S. (1972). "A simple algorithm for merging two disjoint linearly ordered sets." SIAM Journal on Computing, 1(1), 31–39. https://doi.org/10.1137/0201004
4. Barbay, J., & Kenyon, C. (2002). "Adaptive intersection and t-threshold problems." In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), 390–399. https://dl.acm.org/doi/10.5555/545381.545433
5. Auger, N., Jugé, V., Nicaud, C., & Pivoteau, C. (2018). "On the worst-case complexity of TimSort." In 26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs Vol. 112, Article 4. https://doi.org/10.4230/LIPIcs.ESA.2018.4