How Exponential Search Works
Exponential search doubles an index until it passes the target, then binary searches the range it just bracketed. The trick that lets you search a list whose length you do not know.
- Ruled out
- Still possible
- Checked now
- Found
Step 1 of 10
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 10
- steps for this size
Settings
Two to 64 numbers. Sorted ascending before the search runs.
Exponential search
- 1
if a[0] == target: return 0 - 2
- 3
// double the bound until it passes - 4
bound = 1 - 5
while bound < n and a[bound] < target: - 6
bound *= 2 - 7
- 8
// then binary search that span - 9
binarySearch(bound / 2, min(bound, n-1))
The same array, every algorithm
Probes on the values above, cheapest first. One probe is one value actually looked at.
- Interpolation1
- Ternary3
- Binary4
- Jump5
- Exponential8
- Linear13
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
Interpolation search only reaches that average when the gaps between the values are even.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(log i) | O(log i) | O(1) |
i is the target's position, not the list length — which is why this works on an unbounded sequence and beats binary search when the match is near the front.
How exponential search works
Exponential search probes index 1, 2, 4, 8, 16 and so on until it finds a value larger than the target. The target must then lie between the last two probes, a range of at most i elements, which it binary searches. Its cost depends on where the answer is rather than how long the list is, so it can search a sequence with no known end and is faster than plain binary search when matches cluster near the start.
- Check index 0. If it matches, done.
- Set bound to 1, and double it while the value there is still smaller than the target.
- The target now lies between bound/2 and min(bound, n-1).
- Binary search that range.
Implementation
The same algorithm the visualiser is running, written to be read.
def exponential_search(values, target):
n = len(values)
if n == 0:
return -1
if values[0] == target:
return 0
# Double the bound until it passes the target.
bound = 1
while bound < n and values[bound] < target:
bound *= 2
low, high = bound // 2, min(bound, n - 1)
while low <= high:
middle = low + (high - low) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1When to use it
- Use it on unbounded or streamed sorted input, where you cannot ask for the length up front.
- Use it where hits cluster near the beginning — a sorted index whose hot keys are the low ones.
- Use it for merging or intersecting sorted lists: galloping from the last match is exactly this, and it is what makes skip-based intersection fast.
- Avoid it as a general replacement for binary search on a bounded array; when the target sits at the far end, it does the doubling work for nothing.
Check yourself
If the animation made sense, these should too.
Its cost is O(log i) rather than O(log n). Why does that matter?
Because i is the target's position, not the collection's length. That makes it usable on an unbounded or streamed sequence whose length you cannot ask for, and faster than binary search whenever the match is near the front.
Where does this show up outside of array search?
In merging and intersecting sorted lists. Galloping forward from the last match - doubling, then binary searching the bracket - is exactly this algorithm, and it is what makes skip-based list intersection fast in search engines.