Exponential Search

What is exponential search?

Exponential search finds a key in a sorted list in two phases. First it finds a range that must contain the key, by doubling a bound: 1, 2, 4, 8, 16… until the value at the bound is at least the key. Then it runs binary search inside that range.

Why not just use binary search? Because exponential search is fast when the key is near the start, and it works even when you don’t know how long the list is. It is also called doubling search or galloping search.

How it works, step by step

Press play above. In the first phase, the blue bar is the bound being tested against the key; watch it double. Then lo and hi appear around the range, everything outside fades out, and a normal binary search finishes the job.

1. Check the first value. If it is the key, return 0.
2. Set the bound b = 1.
3. While b is inside the list and a[b] is smaller than the key, double it: b *= 2.
4. Now the key, if it is there, sits between b // 2 and b (or the end of the list, whichever comes first).
5. Binary search that range: lo = b // 2, hi = min(b, n − 1).

The doubling phase stops at the first bound that reaches the key. The previous bound, half as big, was still too small, so the key is in between.

Time and space complexity

Let i be the key’s position. The doubling phase takes about log₂ i steps to pass it. The range it finds has about i/2 values, so the binary search takes about log₂ i more. The total is O(log i).

That is the key idea: the cost depends on where the key is, not on how long the list is. A key at position 10 in a list of a billion takes about the same time as in a list of 20.

Best case, O(1): the key is the first value. Worst case, O(log n): the key is near the end, so i is close to n. That makes exponential search never worse than binary search by more than a small constant.

Space is O(1) with a loop-based binary search.

Common mistakes

• Doubling past the end of the list. Check b < len(a) before reading a[b], and clamp hi to n − 1.
• Starting the bound at 0. Doubling 0 stays 0 forever. Check index 0 on its own, then start at 1.
• Searching from 0 to b instead of b // 2 to b. It still works, but throws away the doubling phase’s work.
• Using it on unsorted data. Like binary search, it relies on sorted order.

When to use it

• Unbounded or unknown-length data: a stream, or an API that returns “out of range” instead of a length.
• When the key is likely near the start, like looking up recent entries in a sorted log.
• Merging sorted lists. Timsort, Python’s built-in sort, uses this “galloping” trick to skip over long runs quickly when merging.

For a plain sorted array where the key could be anywhere, binary search is just as good and a little simpler.

Questions

Why is it called exponential search?

The bound grows exponentially: 1, 2, 4, 8, 16, doubling each step.

Is exponential search faster than binary search?

When the key is near the start, yes: O(log i) instead of O(log n). Otherwise they are about the same.

Can exponential search work on an infinite list?

Yes, as long as it is sorted. The doubling phase finds a finite range around the key without ever needing the length.