SearchingAlgorithmaka galloping search, doubling search, Struzik search

Exponential Search

Double an index until the target is bracketed, then binary search inside that bracket.

▶ VisualizePattern: Binary SearchPractice (1)
Progress

Overview

Exponential search finds a target in a sorted array by probing indices 1, 2, 4, 8, … until it finds a[i] ≥ target (or runs off the end), then running Binary Search on [i/2, i]. The cost is O(log i) where i is the target's position — independent of `n`.

That makes it the right tool for unbounded or infinite sorted sequences (a stream, a sorted array whose length you cannot query) and for arrays where the target is likely near the front. TimSort uses the same "galloping" idea to merge runs faster when one run's elements are consistently smaller.

sortedunboundedO(log i)galloping

Intuition

A mental model before the formal terms.

Searching for a house number on an endless street with no map: check house 1, then 2, 4, 8, 16… As soon as you pass the number you want, you know it lies between the last two houses you checked, and that stretch is at most as long as the distance you already walked. Then binary search the stretch.

How it works

  1. If a[0] == target, return 0.
  2. Set i = 1. While i < n and a[i] < target, double i.
  3. The target, if present, lies in [i/2, min(i, n - 1)].
  4. Binary search that range and return the result.

Why it works

Sortedness guarantees that once a[i] ≥ target, no index beyond i can hold a smaller value, and every index below i/2 was already certified < target.

The doubling phase takes ⌈log₂ i⌉ probes and the bracket has length ≤ i/2, so the binary search phase takes another O(log i) — total O(log i).

Recognition

How to tell a problem wants this.

  • A sorted sequence of unknown or infinite length ("the array is infinite", "read-only API returning elements by index").
  • The target is expected to sit close to the start, so log i is much smaller than log n.
  • Merging two sorted sequences of very different sizes, where you want O(m log(n/m)) instead of O(m + n).
“sorted array” → Binary Search

Interactive visualization

Play, step, change the input. ← → and space work too.

2
0
↑bound
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
1/11Check a[0]=2 first. Exponential search then doubles a bound (1, 2, 4, 8...) until a[bound] >= 23, which finds a range of size proportional to the answer's position.
Being compared with targetTarget foundEliminated
PseudocodeLearn Exponential Search →
1if a[0] == target: return 0
2bound = 1
3while bound < n and a[bound] < target: bound *= 2
4lo = bound // 2, hi = min(bound, n - 1)
5binary search target in a[lo..hi]
Variables
target23
Complexity
best O(1)
avg O(log i)
worst O(log n)
space O(1)
Speed

Pseudocode

1if a[0] == target: return 0
2i = 1
3while i < n and a[i] < target: i *= 2
4return binarySearch(a, target, lo = i / 2, hi = min(i, n - 1))

Implementations

1from bisect import bisect_left
2from typing import Callable, Optional, Sequence
3 
4 
51 · Double the bound until it overshoots the target
6def exponential_search(a: Sequence[int], target: int) -> int:
7    n = len(a)
8    if n == 0:
9        return -1
10    if a[0] == target:
11        return 0
12 
13    bound = 1
14    while bound < n and a[bound] < target:
15        bound *= 2
16 
172 · Binary search the bracket (bound/2, min(bound, n-1)] found above
18    lo, hi = bound // 2, min(bound, n - 1)
19    while lo <= hi:
20        mid = (lo + hi) // 2
21        if a[mid] == target:
22            return mid
23        if a[mid] < target:
24            lo = mid + 1
25        else:
26            hi = mid - 1
27    return -1
28 
29 
303 · The point of it: cost depends on the answer position, not the size
31def probes_for(position: int) -> int:
32    doublings = 0
33    b = 1
34    while b < position:
35        b *= 2
36        doublings += 1
37    return 2 * doublings  # ~log2(pos) doublings + ~log2(pos) binary steps
38 
39 
404 · bisect can search the located bracket directly via lo/hi arguments
41def exponential_search_bisect(a: Sequence[int], target: int) -> int:
42    n = len(a)
43    bound = 1
44    while bound < n and a[bound] < target:
45        bound *= 2
46    i = bisect_left(a, target, bound // 2, min(bound + 1, n))
47    return i if i < n and a[i] == target else -1
Walkthrough
  1. bound //= 2 never appears: the bracket is bound // 2 to min(bound, n - 1), computed once after the doubling loop settles.
  2. bisect_left(a, target, lo, hi) takes explicit bounds, so the second phase is a single standard-library call over exactly the bracket found.
  3. The hi argument to bisect_left is exclusive, which is why it is min(bound + 1, n) rather than min(bound, n - 1).
  4. The hand-written version is kept alongside so the mechanism is visible; exponential_search_bisect is what production code should call.
  5. a[0] == target short-circuits index 0, which the bracket [bound // 2, ...] would otherwise exclude.
Complexity (this implementation)
time O(log i) where i is the index of the target · space O(1)

With bisect_left doing phase two in C, the Python-level loop is only the doubling phase — about log2(i) iterations.

Language notes
  • bisect_left(a, x, lo, hi) has taken lo/hi since forever, which makes bracketed binary search a one-liner; the key= parameter arrived in 3.10.
  • Python integers never overflow, so bound *= 2 is safe to any magnitude — the loop is bounded by the sequence length, not by a word size.
  • For a lazily paged source, wrap the accessor in functools.lru_cache so repeated probes at the same index cost one fetch.
  • Sequence[int] rather than list[int] lets the function accept tuples, ranges, and custom sequence types.
Common mistakes in this language
  • Passing min(bound, n - 1) as the hi argument to bisect_left, which is exclusive and therefore excludes the last candidate index.
  • Dropping the index-0 check and returning -1 for a target that sits at the front.
  • Calling bisect_left on an unsorted sequence, which returns a plausible index with no error at all.
Language differences that matter here
  • Out-of-range reads: JS/TS return undefined, which makes the unbounded accessor form natural; C++ is undefined behaviour and Python raises IndexError, so both need an explicit length or a guarded accessor.
  • Phase two is a library call in C++ (std::lower_bound over an iterator sub-range) and Python (bisect_left with lo/hi), and hand-written in JS/TS.
  • Overflow of the doubling bound is a real concern only in C++ with a signed int; JavaScript doubles and Python big integers both stay exact well past any container size.
  • The async variant (paged API, one network probe per step) is idiomatic only in JS/TS, where the accessor can return a Promise.

Complexity

Best
O(1)
Average
O(log i)
Worst
O(log n)
Space
O(1)

i is the index of the target; at most 2·log₂ i + O(1) comparisons.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Sorted data of unknown or unbounded length.
  • Targets biased towards the beginning of the array.
  • Galloping merges of unequal-length sorted runs (as in TimSort) and set intersections of very different sizes.
Avoid it when
  • Bounded arrays with uniformly random targets — plain Binary Search is simpler with the same asymptotics.
  • Unsorted data.
  • Sequences without random access; doubling needs O(1) index access.

Alternatives

Binary SearchJump SearchLinear Search

Common mistakes

  • Using hi = i without clamping to n - 1 after overshooting the array.
  • Starting the binary search at lo = 0 instead of i/2, throwing away the O(log i) guarantee.
  • For an "infinite" array API, forgetting to treat out-of-range reads as +∞.

Interview patterns

  • Search in a sorted array of unknown size: gallop with a read that returns a sentinel past the end.
  • Find the first index k with a[k] ≥ target in a stream that supports random reads.
  • Explain how TimSort's galloping mode uses exponential search to skip long already-ordered stretches during merge.
Interview questions on this
Mock interviews

Example problems

Search in Rotated Sorted Arraymedium