vault

Exponential Search

17 min read

Exponential Search

Exponential search (also called galloping search, doubling search, or Struzik search) finds a target in a sorted sequence of unknown or unbounded length by first locating a bracket that contains the target via geometric doubling, then performing a binary search within that bracket. The cost is O(log i) where i is the position of the target — output-sensitive in a way that classical binary search is not. Exponential search exists for two distinct reasons that are sometimes confused: (1) searching unbounded data, where the array length is not known in advance and ordinary binary search has nothing to bracket against, and (2) searching for elements expected to be near the front, where doubling-then-binary is asymptotically O(log i) instead of O(log n) and dominates classical binary search when i ≪ n. Both motivations stem from the same Bentley & Yao 1976 paper. The technique reappears as the galloping mode inside Tim Sort’s merge phase, where it adaptively accelerates merging when one run dominates the other.

1. Intuition — Probing the Far End First

Suppose you’re searching for a particular paragraph in a very long online document where you can ask “is this word at position k greater than ‘apple’?” but you don’t know how long the document is. Binary search needs lo and hi; you have lo = 0 but no hi.

The natural strategy: probe at position 1. If the word there is still less than ‘apple’, probe at position 2. Then 4. Then 8. Then 16. You’re probing positions that double with each step. As soon as you find a position whose word is ≥ ‘apple’ (or you walk off the end), you’ve established that the target — if it exists — must be in the bracket between your previous probe and this one. Now run an ordinary binary search inside that bracket.

Why doubling? Two reasons that pull in the same direction:

  1. Probes grow geometrically, so the bracket reaches any finite position in O(log i) probes. If the target is at position i, you find it bracketed in roughly ⌈log₂ i⌉ doublings.
  2. The bracket size at the moment you stop is at most i itself, so the binary search inside the bracket is also O(log i). Total: O(log i) + O(log i) = O(log i).

The contrast with classical binary search: classical binary needs to know n and probes the middle of the entire range. Exponential search refuses to commit to a global middle and instead probes outward from the start, paying for the unknown extent with extra probes early. For elements near the start, this is cheaper than blindly halving the unknown infinite tail, because you stop doubling as soon as you’ve overshot.

Bentley and Yao’s original 1976 paper “An almost optimal algorithm for unbounded searching” (Information Processing Letters 5(3): 82–87) gave both the algorithm and a matching lower bound: any algorithm searching an unbounded sorted sequence must use at least log i + log log i + … + Θ(1) comparisons in the worst case for an element at position i. The basic exponential-then-binary scheme matches the leading log i term; a refined scheme called binary-binary search (Bentley & Yao §3) matches all the lower-order terms within a constant.

2. Tiny Worked Example

Consider an unbounded sorted array starting [2, 5, 7, 11, 13, 17, 23, 29, 31, ...] (positions 0 through ∞). Search for target = 17.

Doubling phase — probe at position 1, then double:

ProbePositionValuevalue < target?Action
115yesdouble bound
227yesdouble bound
3413yesdouble bound
4831no — overshotstop, set bracket = [4, 8]

Bracket established: [4, 8]. Run Binary Search inside.

Binary search phase — lo = 4, hi = 8:

SteplohimidvalueAction
14862317 < 23, go left, hi = 5
24541317 > 13, go right, lo = 5
355517match, return 5

Total probes: 4 doublings + 3 binary-search steps = 7. The target was at position 5; classical binary search starting from a known n = ∞ cannot even begin. Notice the bracket size after stopping was 8 − 4 = 4, and ⌈log₂ 4⌉ = 2, matching the binary-search probe count (within ±1 for off-by-ones).

For comparison, if the target is at position i = 1,000,000, doubling phase takes ⌈log₂ 1,000,000⌉ = 20 probes; binary phase searches a bracket of size at most one million, taking another 20 probes. Total ~40 probes vs. ~20 for classical binary search if n were known. Doubling is a constant-factor cost (≈2×) for the privilege of searching unbounded data — a perfectly acceptable price.

3. Pseudocode

exponential_search(arr_or_oracle, target):
    if get(arr, 0) == target:                  # short-circuit position 0
        return 0
    bound := 1
    while get(arr, bound) exists and get(arr, bound) < target:
        bound := bound * 2                     # geometric doubling
    lo := bound / 2                            # we know target ≥ get(arr, lo)
    hi := min(bound, length(arr) - 1) if known else bound
    return binary_search(arr, target, lo, hi)

The contract of get(arr, k) differs by setting:

  • For an in-memory bounded array: get(arr, k) := arr[k] if k < len(arr) else None.
  • For an oracle / online stream: get(arr, k) := query(k) returning the value, or a sentinel like +∞ for out-of-range positions (the LeetCode 702 convention).

The bound / 2 for lo reflects the loop’s invariant: when the loop exits, arr[bound / 2] was the last value confirmed to be < target, so the answer (if it exists) lies in (bound / 2, bound]. Setting lo = bound / 2 is conservative (arr[lo] might equal target, but is guaranteed <= target). Some implementations write lo = bound / 2 + 1 and that’s also correct for strict < doubling; the + 1 shaves one comparison.

4. Python Implementation

4.1 In-Memory Bounded Array

def exponential_search(arr: list[int], target: int) -> int:
    """Return index of target in sorted arr, or -1 if absent."""
    n = len(arr)
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    bound = 1
    while bound < n and arr[bound] < target:
        bound *= 2
    lo, hi = bound // 2, min(bound, n - 1)
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The min(bound, n - 1) clamps hi to a valid index when the doubling overshoots the array length. For an unbounded oracle this clamp is omitted and the binary search internal to the routine relies on the oracle to return a sentinel for out-of-range probes.

4.2 LC 702 — Search in a Sorted Array of Unknown Size

class ArrayReader:
    """Provided by LeetCode: returns arr[k] or 2**31 - 1 for out-of-bounds."""
    def get(self, k: int) -> int: ...
 
 
def search(reader: "ArrayReader", target: int) -> int:
    """Return index of target in the unbounded sorted reader, or -1."""
    SENTINEL = 2**31 - 1
    if reader.get(0) == target:
        return 0
    lo, hi = 0, 1
    while reader.get(hi) < target:
        lo = hi
        hi *= 2                                # exponential doubling
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        v = reader.get(mid)
        if v == target:
            return mid
        elif v < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The reader.get(k) call returning 2**31 - 1 for out-of-bounds positions is the standard LeetCode protocol — the sentinel is treated as ”+∞,” which is > target for any reasonable target, naturally terminating the doubling loop and letting the binary search correctly conclude “not found” when probing past the array end.

The interaction between lo = hi; hi *= 2 is subtle. After the doubling loop exits, we know reader.get(lo) < target (last passing probe) and reader.get(hi) >= target (the failing probe that exited the loop). The binary search bracket is therefore [lo, hi], with lo carrying forward the last good lower bound from the doubling phase rather than restarting at hi // 2. This shaves a couple of comparisons off the constant.

5. Complexity

Time: O(log i) where i is the position of the target (or, if the target is absent, the position where it would be inserted).

The doubling phase: probes go 1, 2, 4, 8, …, 2^k, so the loop exits when 2^k >= i, giving k = ⌈log₂ i⌉ iterations.

The binary search phase: searches a bracket of size at most 2^k − 2^{k-1} = 2^{k-1} ≤ i, taking O(log i) comparisons.

Total: O(log i). Notice this is output-sensitive in i, not in n. For elements near the front of a very long array, exponential search is asymptotically faster than classical binary search; for elements at the end, it’s a constant factor (≈2×) slower because the doubling phase is essentially redundant work that classical binary would have skipped.

Space: O(1) iterative; O(log i) if the binary search inside is recursive.

Comparison with binary search. If n is known and the target’s position is uniformly distributed:

  • Classical binary search: always ⌈log₂ n⌉ ± 1 comparisons.
  • Exponential search: 2 × ⌈log₂ i⌉ ± 1 comparisons, ranging from ~2 (target at position 1) to ~2 log n (target at the end).

Expected case (uniform i): exponential search averages ~2 × (log n - 1) comparisons, marginally worse than binary. Worst case (target at end): exactly 2× worse. Best case (target at start): dramatically better — O(log i) for small i is constant for i = O(1), vs. Θ(log n) for binary regardless of i. The choice between them is therefore not “which is faster” but “what’s the access model.”

6. When Exponential Search Is the Right Choice

The technique earns its place in the toolkit in three distinct scenarios:

6.1 Unbounded / Unknown-Length Sequences

This is the LC 702 use case. The array length is not known to the caller — the only operation is get(k), which returns the value at position k or a sentinel for out-of-range. Classical binary search needs both lo and hi; exponential search builds the hi for you. Common in stream-like data sources, virtual arrays, mmap’d files of unknown extent, and abstract sorted iterators.

6.2 Adaptive Searching with Skewed Position Distribution

If the target is expected to be near the front (e.g., recently-accessed items in an LRU-ordered list, or merging two sorted runs where one is much larger than the other), the O(log i) cost dominates the O(log n) cost when i ≪ n. This is exactly the situation that motivated Tim Sort’s galloping mode.

6.3 As a Subroutine in Tim Sort’s Merge Phase

Tim Peters’s Tim Sort (the standard sort in CPython, V8, and the JDK since Java 7) uses exponential search inside its merge step. When merging two sorted runs A and B, the standard linear merge becomes wasteful if one run consistently wins: if A[0] < A[1] < ... < A[k] are all less than B[0], a linear merge takes k comparisons to copy the prefix of A, where exponential search inside A for the bracket containing B[0] would take O(log k). Tim Sort detects this regime (“if one side has won 7 times in a row, switch to galloping”) and uses exponential search to find the bracket, then binary search inside it to find the exact insertion point. This is why Tim Sort beats merge sort on partially-ordered data — galloping skips over already-ordered runs in logarithmic time. The detailed protocol and the threshold of 7 are documented in Peters’s original timsort.txt design note (linked in sources).

7. Variants and Refinements

7.1 Binary-Binary Search (Bentley & Yao §3)

The basic scheme uses 2 × ⌈log₂ i⌉ ± 1 comparisons. Bentley and Yao showed you can do better: after the doubling phase locates the bracket, instead of running a normal binary search, recursively exponential-search inside the bracket using the bracket size as the new “unknown bound.” This saves the lower-order log log i terms and matches the information-theoretic lower bound to within a constant. Rarely worth the implementation complexity in practice; the basic 2×-binary-search constant is good enough.

7.2 Galloping with Adaptive Step Size

The constant doubling factor of 2 is convenient but arbitrary. Some implementations use a larger factor (e.g., 4, or even i^{1.5}) to reduce the number of probes in the doubling phase at the cost of a larger bracket in the binary phase. The optimal factor depends on the relative cost of probes vs. comparisons in the binary phase; for in-memory arrays the difference is negligible.

Interpolation Search estimates the target’s position from the values at the bracket endpoints (assuming approximately uniform value distribution) — O(log log n) expected on uniform data, but degenerates to O(n) on adversarial input. Exponential search has worse asymptotics (O(log n) not O(log log n)) but is robust to non-uniform distributions. Use interpolation when you trust the data distribution; use exponential when you don’t, or when the data is unbounded.

An alternative to doubling: probe at position 1, then 2, then 3, … (linear walk) until you overshoot, then binary-search the bracket. This is O(i) not O(log i) — strictly worse than exponential search for any i > 4. Mentioned only because it’s the “obvious” thing to try and exponential search’s elegance is in choosing geometric instead of arithmetic step sizes.

8. Pitfalls

8.1 Off-by-One on the Initial Probe

Starting bound = 1 instead of bound = 0 is intentional: position 0 was already checked in the short-circuit, and bound = 0 would loop forever (0 * 2 = 0). The short-circuit + bound = 1 start is the idiom; bound = 0; bound = bound * 2 + 1 is a less-common alternative.

8.2 Failing to Handle the Sentinel

For unbounded arrays returning a sentinel (2**31 - 1 in LC 702, or +∞ in some abstractions), the doubling loop’s comparison arr[bound] < target works correctly as long as target < sentinel. If target == sentinel, the doubling loop exits immediately at bound = 1 (incorrectly thinking the target is beyond), and the binary search returns -1. For LC-style problems where targets are bounded below the sentinel, this is fine; in production code, validate the target against the sentinel at the top of the function.

8.3 Forgetting to Clamp hi for Bounded Arrays

If you adapt the unbounded variant for a bounded array, doubling can carry bound past n - 1. The binary search must use hi = min(bound, n - 1). Forgetting the clamp produces an IndexError on probes past the array end.

8.4 Using It When n Is Known and Small

For known n and uniformly-distributed i, classical binary search has slightly fewer comparisons. Exponential search shines when either n is unknown or i ≪ n is expected. Defaulting to exponential search “just in case” trades simplicity for a marginal worst-case slowdown — usually not worth it.

In Tim Sort literature “galloping” means the same as “exponential search” in algorithms texts. They’re synonyms (with the niche exception that “galloping” sometimes implies the doubling factor is variable, not fixed at 2). If a reference says “galloping mode” without further specification, assume exponential-then-binary search.

8.6 Doubling Past 2³¹ on 32-bit Integers

bound *= 2 overflows on 32-bit signed integers when bound ≥ 2³⁰. For Python this doesn’t matter; for C/Java it does. Cap the doubling explicitly (bound = min(bound * 2, INT_MAX)) or use unsigned arithmetic.

9. Diagram — Two Phases

flowchart LR
    subgraph phase1 ["Phase 1: Geometric Doubling"]
        P0["bound=1"] -->|"arr[1] < target"| P1["bound=2"]
        P1 -->|"arr[2] < target"| P2["bound=4"]
        P2 -->|"arr[4] < target"| P3["bound=8"]
        P3 -->|"arr[8] ≥ target — STOP"| P4["bracket = [4, 8]"]
    end
    subgraph phase2 ["Phase 2: Binary Search Inside Bracket"]
        B0["lo=4, hi=8, mid=6"] -->|"arr[6] > target"| B1["lo=4, hi=5"]
        B1 -->|"arr[4] < target"| B2["lo=5, hi=5 — match"]
    end
    P4 --> B0

What this diagram shows. The top row depicts the doubling phase from the §2 worked example. Each box represents one probe; the doubling continues as long as the probed value is less than the target. When the probe at position 8 returns a value ≥ target, the doubling loop exits, having established that the answer must lie in the bracket [4, 8] — 4 because that was the last position whose value was less than the target, and 8 because that was the first position whose value was at least the target. The bottom row depicts the standard Binary Search applied to that bracket, halving the search space until the target is located at position 5. The arrow from P4 to B0 shows the handoff between phases. The total comparison count is the sum of the two phases, both of which are O(log i). Notice that Phase 1 cannot be done with binary search — there is no hi to bisect against until Phase 1 produces one — and Phase 2 could be done by continuing the doubling-style probe but at higher constant cost than ordinary binary search inside a known bracket. The two phases are a clean separation of concerns: doubling discovers the bracket, binary refines within it.

10. Common Interview Problems

#ProblemWhy exponential search
LC 702Search in a Sorted Array of Unknown SizeCanonical: array length unknown, only get(k) available
LC 35Search Insert PositionCould use exponential when target is expected near front; usually plain binary
LC 4Median of Two Sorted ArraysGalloping ideas appear in some advanced solutions; not the standard approach
LC 540Single Element in a Sorted ArrayPlain binary; mentioned for contrast
(system design)“Searching a log file of unknown size”Exponential search is the textbook answer
(Python internals)Understanding list.sort() performanceTim Sort uses galloping; exponential search is the merge-phase accelerator
(database internals)B+ tree leaf scans for skewed range queriesGalloping appears in some merge-join implementations

LC 702 is the only LeetCode problem that specifically requires exponential search to be tractable — most others are bounded and binary search suffices. The technique earns its keep more in systems contexts (log-search, merge-join, sort internals) than in classic algorithm interviews.

11. Open Questions

  • Which modern sorts besides Tim Sort use galloping in their merge phase? Powersort — designed by J. Ian Munro and Sebastian Wild, and the default list.sort() in CPython since version 3.11 (also adopted by PyPy, AssemblyScript, and Apple’s WebKit) — keeps Timsort’s galloping merge: “Each merge step combines two adjacent runs into a single one using a ‘galloping strategy’: exponential search is used to find the prefix of one run that precedes the minimum in the other run” (Wikipedia: Powersort). Notably, Rust’s stable sort went the other way: the 2024 rewrite (driftsort) deliberately dropped galloping because the “complex galloping procedures in hot loops” hurt performance on random inputs, trading that adaptivity for speed on the common case (rust-lang/rust PR #90545). So galloping is not universal even among Timsort descendants — it is a deliberate trade-off favoring partially-ordered inputs over random ones. (An earlier version of this note misattributed Powersort to Rust; Powersort is Python’s, and Rust’s current sort has no galloping.)
  • Are the lower-order log log i + log log log i + … terms in Bentley-Yao’s lower bound ever tight in practice? Possibly for specialized hardware or specific data distributions; in general, the basic 2 log i upper bound from exponential-then-binary is what’s used.
  • How does exponential search compose with Skip List and Binary Indexed Tree (Fenwick Tree) traversals? Both use power-of-two strides for similar reasons; the connection is intuitive but I’m not aware of a unified treatment.

Uncertain uncertain

Verify: that exponential search, skip-list search, and Fenwick-tree (binary indexed tree) traversal are instances of a single underlying “geometric/power-of-two stride” search principle. Reason: this is a speculative synthesis, not a claim found in any primary source consulted for this note; the surface resemblance (all three use doubling/halving strides) may be coincidental rather than a formal unification. To resolve: locate a paper or textbook that formally relates these structures (e.g. via the implicit binary-tree view of a skip list, or the binary-decomposition view of Fenwick indices), or establish that no such unified treatment is standard.

12. See Also

Graph View

Backlinks