Exponential Search
Doubles its reach (1, 2, 4, 8, …) through a sorted array until it passes the target, then binary searches the range it skipped.
SearchingDivide and conquerSorted inputO(log n)
How it works
Exponential search works on a sorted array in two phases.
- Find the range. It checks index 0, then indexes 1, 2, 4, 8, 16, …, doubling each time, while the value there is smaller than the target. As soon as it reaches a value that isn't smaller (or runs off the end), the target can only be between the previous index and this one.
- Binary search. It runs a normal binary search on just that range.
If the target is at index i, the doubling stops after about log₂ i steps, and the range it found is only about i / 2 long, so the binary search takes about log₂ i steps too.
When to use it
Exponential search shines when the target is likely to be near the start, since its cost depends on where the target is (i), not on the size of the array (n). It also works on unbounded or very long sorted lists, like an infinite stream or a sorted file whose length you don't know: binary search needs a high end to start from, and the doubling finds one.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is the first value |
| Average | O(log i) | i is the target's index: doubling plus binary search |
| Worst | O(log n) | The target is near the end, or isn't there at all |
| Extra space | Why |
|---|---|
| O(1) | It only keeps the bound and the binary search's low, high and mid |
Implementations
function exponentialSearch(array, target) {
const n = array.length;
if (n === 0) return -1;
if (array[0] === target) return 0;
let bound = 1;
while (bound < n && array[bound] < target) {
bound *= 2;
}
let low = Math.floor(bound / 2);
let high = Math.min(bound, n - 1);
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const value = array[mid];
if (value === target) return mid;
if (value < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
def exponential_search(array, target):
n = len(array)
if n == 0:
return -1
if array[0] == target:
return 0
bound = 1
while bound < n and array[bound] < target:
bound *= 2
low, high = bound // 2, min(bound, n - 1)
while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
if array[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
#include <algorithm>
#include <vector>
int exponentialSearch(const std::vector<int>& a, int target) {
const int n = static_cast<int>(a.size());
if (n == 0) return -1;
if (a[0] == target) return 0;
int bound = 1;
while (bound < n && a[bound] < target) {
bound *= 2;
}
int low = bound / 2;
int high = std::min(bound, n - 1);
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}