Overview
Exponential Search finds a target in a sorted array by first locating a range that must contain it, then running Binary Search inside that range. It starts at index 1 and repeatedly doubles the bound until it passes the target.
This doubling phase quickly brackets the target near the front of the array, which makes Exponential Search especially attractive for unbounded or very large sorted inputs where the target tends to be close to the beginning.
How Exponential Search works
- Check index 0 first; if it holds the target, return immediately.
- Start with a bound of 1 and double it (1, 2, 4, 8, …) while the element at the bound is still below the target.
- Stop once the bound's value meets or exceeds the target, or the bound leaves the array.
- This gives a range between the previous bound and the current bound that must contain the target.
- Run Binary Search within that bounded range to find the exact index.
When to use it
- Unbounded or streaming sorted data whose length is unknown in advance.
- Very large sorted arrays where the target is expected near the beginning.
- As a bounding front-end that hands a small, known range to Binary Search.
Complexity analysis
If the target sits at index i, the doubling phase takes O(log i) steps to bracket it, and the following Binary Search over that range is also O(log i), giving O(log n) time overall in the worst case. It requires a sorted array and uses O(1) extra space when iterative.
Frequently asked questions
Why use Exponential Search instead of plain Binary Search?
It shines when the array length is unknown or effectively unbounded: the doubling phase discovers a valid range without needing the total size up front, then delegates to Binary Search.
Is Exponential Search faster than Binary Search?
Both are O(log n), but Exponential Search can be faster when the target is near the front, since it finds a tight bounding range in O(log i) steps proportional to the target's position.