An algorithm used for searching in sorted, unbounded arrays. It involves two steps: first finding a range where the element could be, and then performing a binary search within that range.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
{
"arr": "[2, 3, 4, 10, 40]",
"target": 10,
"n": 5
}Overview
Exponential Search, also called galloping or doubling search, first finds a range that must contain the target and then runs binary search inside that range. It checks indices 1, 2, 4, 8, 16, … until it finds an element larger than the target or runs off the end.
Because the range doubles each time, finding it takes O(log i) steps, where i is the position of the target. That makes it better than plain binary search when the target is near the start, and it works even when the array length is unknown or unbounded.
In the default example (2, 3, 4, 10, 40, target 10), index 0 does not match, so i grows 1 → 2 → 4. At index 4 the value 40 is larger than 10, so binary search runs on indices 2..4 and finds 10 at index 3.
Step by step
- If
arr[0]is the target, return 0. - Set
i = 1; whilei < nandarr[i] <= target, doublei. - Run binary search on the range
floor(i / 2)..min(i, n - 1). - Return the binary search result.
Complexity
| Case | Cost | Why |
|---|---|---|
| Best case | O(1) | The target is at index 0. |
| Average case | O(log i) | i is the target position; both phases are logarithmic in i. |
| Worst case | O(log n) | Target near the end. |
| Extra space | O(1) | Iterative binary search phase. |
When to use it
- Unbounded or very large sorted sequences, such as an infinite stream or an API without a length.
- When targets are usually near the beginning.
- The galloping step in Tim Sort's merge uses this same idea.
Common mistakes
- Starting at
i = 0means doubling never moves (0 × 2 = 0); start at 1. - The binary-search bounds must be clamped to
n - 1. - It still requires sorted input.
A dry run is the best way to check your understanding of Exponential Search: follow each row, predict the next one, and compare. The run below takes 13 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- 2,3,4,10,40
- Target
- 10
- Result
- return value = 3
| Step | Line | Array | What happens |
|---|---|---|---|
| 1 | 1 | [2, 3, 4, 10, 40] | target = 10, n = 5 |
| 2 | 2 | [2, 3, 4, 10, 40] | condition = 2 == 10 |
| 4 | 6 | [2, 3, 4, 10, 40] | i = 1, n = 5, condition = 1 < 5 && 3 <= 10 |
| 6 | 6 | [2, 3, 4, 10, 40] | i = 2, n = 5, condition = 2 < 5 && 4 <= 10 |
| 8 | 6 | [2, 3, 4, 10, 40] | i = 4, n = 5, condition = 4 < 5 && 40 <= 10 |
| 9 | 10 | [2, 3, 4, 10, 40] | from = 2, to = 4, status = Calling Binary Search |
| 10 | 16 | [2, 3, 4, 10, 40] | low = 2, high = 4, condition = 2 <= 4 |
| 12 | 18 | [2, 3, 4, 10, 40] | mid = 3, arr[mid] = 10, target = 10, condition = 10 === 10 |
| 13 | 19 | [2, 3, 4, 10, 40] | return value = 3 |