Home/Searching/Exponential search
Search algorithmsCTRL K

Exponential search

· double the bound, then binary search
/searching/exponential-search
COMPARISONS
1
probes so far
BOUND
1
1, 2, 4, 8, … until past the target
RANGE
2/ 32
elements still possible
MIDDLE
0
probe of the binary phase
RESULT
—
index once found
discardedprobetargetfound
n = 32 · target 33 · seed 7 · unbounded · 12 steps
step 0 / 11
Size32
exponential_search.ts
1
function exponentialSearch(array: number[], target: number) {
2
  if (array[0] === target) return 0;
3
  let bound = 1;
4
  while (bound < array.length && array[bound] < target) bound *= 2;
5
  let low = Math.floor(bound / 2), high = Math.min(bound, array.length - 1);
6
  while (low <= high) {
7
    const middle = (low + high) >> 1;
8
    if (array[middle] === target) return middle;
9
    if (array[middle] < target) low = middle + 1;
10
    else high = middle - 1;
11
  }
12
  return -1;
13
}
CURRENT STEP
line 2

Look for 33. First check array[0] = 7, not it.

// how it works

Understanding Exponential search

exponential search · find the neighbourhood by doubling, then halve inside it
01

The idea

Exponential search first finds a range that must contain the target by probing indices 1, 2, 4, 8, … until the value there is at least the target. The target then lies between the last two bounds, a range of at most half the bound, and a binary search finishes the job.

The cost is 2 log i for a target at index i, not log n: a target near the front is found quickly whatever the array size, and the array does not even need a known size. That makes it the standard way to search unbounded or infinite sorted streams.

02

The four stages

1
doublebound ← 2 × bound while array[bound] < target
2
bracketthe target is in [bound / 2, bound]
3
halvebinary search inside the bracket
4
foundor the bracket empties
03

Complexity

best
O(1)the target is the first element
average
O(log i)i the target's index, not n
worst
O(log n)target at the end: 2 log n probes
space
O(1)a bound and two indices
04

Versus its siblings

PROBES AT N = 1 000 000 · TARGET AT INDEX 100
exponential
14
binary
20
interpolation
5
jump
1,100
linear
101
exponential and linear depend on where the target is, the others on n
05

Pseudocode

EXPONENTIALSEARCH(array, target)
  if array[0] = target: return 0
  bound ← 1; while bound < n and array[bound] < target: bound ← 2 × bound
  low ← bound / 2; high ← min(bound, n − 1)
  binary search for target inside [low, high]
06

When to use

Unbounded or lazily produced sorted sequences: infinite streams, files read from the front, results of a generator.
Searches where the target is usually near the beginning, such as merging a small sorted list into a huge one.
07

Pitfalls

Clamp the bound to n − 1 when the array is finite, or the probe runs off the end.
The binary phase must start at bound / 2, not at 0, or the doubling was wasted.
For targets near the end it costs twice binary search; use it when the position is unknown or the array unbounded.
08

History

Jon Bentley and Andrew Yao described it in 1976 as a search for unbounded sorted lists, also called galloping or doubling search. Peter McIlroy's 1993 merge and Tim Peters's Timsort use galloping to merge runs of very different lengths in near-linear time.

Back to Searching