Exponential search
mediumBuilt for unbounded or unknown-length input - an infinite stream, or an API you can only probe by index. Costs O(log i) where i is where the target actually is.
O(1)Average O(log i)Worst O(log n)Space O(1)What to notice
Built for unbounded or unknown-length input
Binary search needs n up front. Exponential search does not - it discovers a bound by doubling, which works on an infinite stream or an API you can only probe by index.
O(log i), not O(log n)
The cost depends on where the target is, not how big the array is. For a target near the front of a huge sorted array this beats binary search outright.
Saved in this browser - no sign-up, nothing sent anywhere.
How exponential search works
Binary search needs to know n before it can probe a middle. Exponential search does not: it probes indices 1, 2, 4, 8, 16, doubling until it finds a value above the target. That makes it the search for unbounded input - an endless sorted stream, or an API you can only query one index at a time.
When the doubling overshoots at index bound, the previous probe at bound/2 was still at or below the target - so the answer is trapped in a[bound/2 .. min(bound, n - 1)]. That window holds about i elements, where i is the target's true position, and an ordinary inclusive binary search finishes inside it.
The cost is O(log i), not O(log n): about log i doublings to find the window, then log i more binary steps inside it. Position matters, array size does not - a target near the front of a billion-element array falls in a handful of probes. The same idea, under the name galloping, drives Timsort's merge step.
Step by step
- Search for 23 in the 18-element sorted array. a[0] = 3 is checked first - the doubling loop starts at index 1 and would never see it.
- a[1] = 8 <= 23, so double the bound to 2. a[2] = 12 <= 23, double again to 4.
- a[4] = 23 is still not above the target - the loop condition is <=, so it doubles to 8 even though the probe just touched the answer.
- a[8] = 47 exceeds 23. The window is a[4..8]: lo = bound/2 = 4, hi = min(8, 17) = 8.
- Binary search that window: mid = 6, and a[6] = 34 > 23 pulls hi down to 5.
- mid = 4, a[4] = 23 - found at index 4. Seven comparisons in total: one start check, four doubling probes, two binary steps.
Complexity
| Best case time | O(1) |
|---|---|
| Average time | O(log i) |
| Worst case time | O(log n) |
| Space | O(1) |
Reference implementation
Python
def exponential_search(a, target):
n = len(a)
if n == 0:
return -1
if a[0] == target:
return 0
bound = 1
while bound < n and a[bound] <= target:
bound *= 2 # doubling reach
lo, hi = bound // 2, min(bound, n - 1)
while lo <= hi: # ordinary binary search
mid = lo + (hi - lo) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1JavaScript
function exponentialSearch(a, target) {
const n = a.length;
if (!n) return -1;
if (a[0] === target) return 0;
let bound = 1;
while (bound < n && a[bound] <= target) bound *= 2;
let lo = bound >> 1, hi = Math.min(bound, n - 1);
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (a[mid] === target) return mid;
if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
}
return -1;
}Common pitfalls
- Binary searching a[0..n-1] instead of a[bound/2..bound] after the doubling - still correct, but the cost snaps back to O(log n) and the whole point is lost.
- Forgetting min(bound, n - 1): the doubling usually overshoots the array's end, and using bound directly as hi indexes out of bounds.
- Skipping the a[0] check. The doubling loop starts at index 1, so a target at index 0 - or an empty array - must be handled before it runs.
- In fixed-width integers, doubling bound can overflow to a negative number on arrays near the type's limit - guard the doubling the same way you guard midpoints.
Where it is used
- Unbounded search: locating a value in an infinite sorted stream, or an API you can only probe index by index.
- Timsort's galloping mode - Python's and Java's built-in sorts use it to merge runs of very different sizes.
- Huge sorted arrays where targets cluster near the front: O(log i) beats O(log n) outright.
- The interview question 'search in a sorted array of unknown size' is this algorithm verbatim.
Frequently asked questions
What is the time and space complexity of exponential search?
Best case O(1) when a[0] or an early probe hits; average O(log i), where i is the index the target actually occupies; worst case O(log n) when it sits at the far end. Both the doubling phase and the binary search contribute about log i comparisons. Space is O(1).
How is exponential search different from binary search?
Binary search needs the length up front and always pays O(log n). Exponential search discovers its own upper bound by doubling, so it works on unknown-length or unbounded input and costs O(log i) - cheaper whenever the target sits near the front. Its final phase is a plain binary search.
Why is exponential search also called galloping search?
The probe positions 1, 2, 4, 8, 16 accelerate like a gallop. The name stuck through Timsort, which gallops during merges: when one run keeps winning, it doubles its stride to measure the streak, then binary searches the final stretch it overshot.
Why does the binary search cover a[bound/2] to a[bound]?
The doubling loop stopped because a[bound] exceeded the target - and the previous probe at bound/2 was still at or below it. Those two facts bracket the target between them. The window holds about i elements, which is exactly what makes the total cost O(log i).