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
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
More options
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 |
Scroll the table sideways for the rest of the columns.
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) |
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
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 -1