Exponential Search: Locating a Target in an Unbounded Sorted Array

The core idea and its invariant

Exponential search runs in two phases that compose cleanly. First a range-finding phase discovers a bracket [lo, hi] that is guaranteed to contain the target (or to prove its absence); then a binary-search phase pinpoints it inside that bracket. The elegance is that the first phase spends effort proportional to where the answer is, not to how big the array is.

Let A be sorted ascending and key the target. The range-finding phase maintains a single moving index bound, doubling it each step:

• Invariant: at the start of iteration k (for k ≥ 1), bound = 2ᵏ, and every element in A[0 .. bound/2] is strictly less than key — we reached this bound only because the previous probe found A[bound/2] < key. Equivalently, the target — if present — lies at index > bound/2.
• Termination condition: stop the moment bound ≥ n (ran off the end) or A[bound] ≥ key (overshot the target). At that instant the answer, if any, is trapped in [bound/2, min(bound, n−1)].

Because the array is sorted, A[bound] ≥ key means we have jumped past — or exactly onto — the target, and A[bound/2] < key (from the invariant) means we have not jumped so far as to skip it. That two-sided sandwich is precisely what binary search needs.

How it works, step by step

The algorithm handles the index-0 case first (a common off-by-one trap), then gallops, then delegates:

• Check the front: if A[0] == key, return 0. This special-case guarantees the doubling loop can safely start at bound = 1 without bound/2 underflowing.
• Gallop: starting from bound = 1, while bound < n and A[bound] < key, set bound *= 2. Each doubling costs exactly one comparison.
• Bracket: set lo = bound / 2 and hi = min(bound, n − 1). The target lies in [lo, hi] or nowhere.
• Binary search the sub-array A[lo .. hi] and return the index (or −1 / the insertion point).

function exponentialSearch(A, n, key):
    if n == 0: return -1
    if A[0] == key: return 0
    bound = 1
    while bound < n and A[bound] < key:
        bound = bound * 2
    lo = bound / 2
    hi = min(bound, n - 1)
    return binarySearch(A, lo, hi, key)

For a genuinely unbounded source (no known n — say a virtual array backed by a function or a paginated fetch), drop the bound < n guard and instead treat an out-of-range access as a sentinel of +∞: get(bound) returns a value ≥ key the moment the index passes the end, which naturally halts the gallop.

Complexity analysis and derivation

Let the target sit at index i (or, if absent, let i be its insertion point). The gallop doubles until bound > i, which first happens when 2ᵏ > i, i.e. after k = ⌊log₂ i⌋ + 1 iterations. That's Θ(log i) comparisons for the range-finding phase.

• Binary-search phase: the bracket [bound/2, bound] has width bound/2 ≈ i, so binary search over it costs log₂(bound/2) = Θ(log i) comparisons.
• Total: Θ(log i) + Θ(log i) = Θ(log i). Concretely the comparison count is about 2·⌊log₂ i⌋ — twice binary search's log — but binary search's log is over n, not i.

When is exponential search faster? Whenever 2·log₂ i < log₂ n, i.e. i < √n. If the target lives in the first √n elements of a billion-element array, exponential search wins on comparisons; if it lives in the far tail it does at most ~2× the work of a plain binary search — a small, bounded penalty. In the worst case i = n, giving O(log n), matching binary search up to the constant factor of 2.

Space is O(1) for the iterative form (just the bound, lo, hi indices); a recursive binary-search tail would add O(log i) stack frames unless written tail-recursively or as a loop.

Trade-offs and when to reach for it

Exponential search is not a general replacement for binary search — it's the tool for a specific shape of problem. Pick it when at least one of these holds:

• The length is unknown or infinite. This is the canonical use: LeetCode's "Search in a Sorted Array of Unknown Size", a sorted stream behind an iterator, or a function f(i) that is monotonic over an unbounded domain. Binary search cannot even initialize hi here.
• Access is cheap near the front, expensive far away. Paginated REST APIs, on-disk sorted files where early pages are cached, or skip-lists where the target is usually recent — all reward a search whose cost scales with i, not n.
• Queries are front-loaded. If your access pattern is skewed so most targets are small-index, the amortized cost over many queries is far below log n.

The chief caveat is the constant factor: for a target in the middle or tail of a known-length array, plain binary search does strictly fewer comparisons (log n vs ~2 log n). Exponential search also inherits binary search's requirements — the data must be sorted and support O(1) random access by index. It is useless on a linked list (no indexing) and pointless on unsorted data.

Where it runs in real systems

The doubling-probe idea is one of the most reused primitives in systems code, even where it isn't called "exponential search" by name:

• Timsort's galloping mode (Tim Peters' Python sort, also Java's Arrays.sort for objects and Android/OpenJDK): when merging two runs and one run keeps winning, the merge switches to galloping — an exponential search to find how many elements to copy in bulk. This turns O(k) linear merge steps into O(log k), the single biggest constant-factor win over classic merge sort on partially ordered data.
• Dynamic arrays (std::vector, Java ArrayList, Go slices, Python list) grow capacity by doubling — the same exponential schedule, which is why append is amortized O(1). The analysis is the mirror image of exponential search's log-i bound.
• Sorted-file and index lookups: searching an on-disk sorted run or a column-store block of unknown local length uses doubling to bracket before a precise probe, minimizing cold I/O near the front.
• Unbounded monotone predicates: "find the smallest N where server(N) starts failing" or binary-searching a rate limit / capacity threshold with no known upper bound — you exponentially probe up to find a ceiling, then binary search down.

The original analysis is due to Jon Bentley and Andrew Chi-Chih Yao, "An Almost Optimal Algorithm for Unbounded Searching" (Information Processing Letters, 1976), which also introduced the sharper unbounded search variants that shave the constant further.

Pitfalls, edge cases, and variants

The algorithm is short, which lulls people into shipping subtle bugs. The recurring failure modes:

• Off-by-one at index 0: starting the gallop at bound = 0 makes 0 * 2 = 0 — an infinite loop. Start at bound = 1 and special-case A[0], or start at bound = 1 and use lo = bound / 2 which safely yields 0.
• Clamping hi: after the gallop, bound may exceed n − 1. Always pass hi = min(bound, n − 1) to the binary search or you index out of bounds.
• Integer overflow: repeated bound *= 2 on a 32-bit int overflows past ~2³¹. Use a 64-bit index, or bound the doubling with bound < n before multiplying.
• Empty array: guard n == 0 up front; otherwise A[0] faults.
• Duplicates: vanilla exponential search returns some matching index. For "leftmost/rightmost occurrence", pair the gallop with a lower-bound / upper-bound binary search inside the bracket.

Variants worth knowing. Galloping/one-sided binary search is the same idea used to search near a known pivot both left and right. Fibonacci search replaces doubling with a Fibonacci-ratio schedule to favor cheaper comparisons on sequential-access media. And for the unbounded case with a known distribution, one can splice in interpolation search inside the bracket for O(log log i) expected time on uniform data — though that gambles worst-case O(i) if the distribution is adversarial.

Exponential search versus the standard sorted-array search alternatives

Algorithm	Needs length n?	Time (target at i)	Worst case	Probes when i ≪ n
Binary search	Yes	O(log n)	O(log n)	~log₂ n (fixed)
Exponential search	No	O(log i)	O(log n)	~2·log₂ i
Linear scan	No	O(i)	O(n)	i comparisons
Interpolation search	Yes	O(log log n) avg (uniform)	O(n)	depends on distribution
Galloping (Timsort)	No	O(log i)	O(log n)	~2·log₂ i per gallop