SearchingSearching

Exponential Search

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

Learn Exponential Search →
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