What is Exponential Search?
Learn how exponential search doubles an index to bracket a target then binary searches it, and how to answer this interview question.
Expected Interview Answer
Exponential search finds a target in a sorted array by first doubling an index (1, 2, 4, 8, ...) until it finds a range that must contain the target, then running binary search inside just that range — giving O(log p) complexity where p is the target's actual position, which beats plain O(log n) binary search when the target is near the front of an unbounded or very large array.
The algorithm starts by checking arr[0], then probes arr[1], arr[2], arr[4], arr[8], doubling the index each time, until either it overshoots the array bounds or arr[index] exceeds the target. That last doubling step establishes a range [index/2, min(index, n-1)] guaranteed to contain the target if it exists, and binary search runs only inside that narrow range instead of the whole array. This makes exponential search especially valuable for unbounded or streaming sorted data where the total size n is unknown — you never need to know n up front, only when to stop doubling. It is also used to speed up binary search when the target is expected to be near the beginning, since the range found is proportional to the target's position, not the whole array size.
- O(log p) where p is the target position, better than O(log n) near the front
- Works on unbounded or unknown-length sorted sequences
- Combines cheaply with standard binary search for the final narrow scan
- No need to know array length n in advance
AI Mentor Explanation
A scorer looking for the over in which a specific run milestone was reached does not scan every over from one — they check over 1, then over 2, then over 4, then over 8, doubling each time, until the milestone's over number is bracketed between the last two checks. Only then do they binary search within that narrow bracket of overs instead of the whole innings. If the milestone happened early, like over 3, this doubling approach finds the bracket almost immediately instead of stepping through every over. This is exactly exponential search — doubling outward to find a bracket, then binary searching only inside it.
Step-by-Step Explanation
Step 1
Check the first element
If arr[0] equals the target, return immediately.
Step 2
Double the index outward
Probe index 1, 2, 4, 8, ... doubling until arr[index] exceeds the target or index goes past the array bounds.
Step 3
Establish a bracket
The target, if present, must lie between index/2 and min(index, n-1).
Step 4
Binary search inside the bracket
Run standard binary search only within that narrow bracket instead of the full array.
What Interviewer Expects
- Explain the doubling phase and why it stops
- Correctly derive the bracket range passed to binary search
- State the complexity as O(log p), where p is the target position
- Name the unbounded/streaming array use case as the key motivation
Common Mistakes
- Confusing exponential search with an algorithm that runs in exponential time (it does not — it is logarithmic)
- Forgetting to bound the doubling probe against array length, causing an out-of-bounds read
- Assuming exponential search beats binary search for targets near the end of the array (it does not)
- Running binary search over the whole array instead of just the discovered bracket
Best Answer (HR Friendly)
“Exponential search finds a target in a sorted array by doubling my probe index — 1, 2, 4, 8 — until I've bracketed where the target must be, then running binary search inside just that small bracket. It's especially useful when I don't know the array's length ahead of time, like scanning a stream, or when the target is likely near the start.”
Code Example
def binary_search(arr, lo, hi, target):
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def exponential_search(arr, target):
n = len(arr)
if n == 0:
return -1
if arr[0] == target:
return 0
index = 1
while index < n and arr[index] <= target:
index *= 2
lo = index // 2
hi = min(index, n - 1)
return binary_search(arr, lo, hi, target)Follow-up Questions
- How would you adapt exponential search for a truly unbounded stream with no known upper limit?
- Why is exponential search called "exponential" if its complexity is logarithmic?
- In what scenario does exponential search perform worse than plain binary search?
- How would you handle exponential search on a descending sorted array?
MCQ Practice
1. What is the time complexity of exponential search, where p is the position of the target?
The doubling phase takes O(log p) steps and the subsequent binary search inside the bracket also takes O(log p), so total complexity is O(log p).
2. What is the primary use case that motivates exponential search over plain binary search?
Exponential search never needs to know the array length upfront, making it ideal for unbounded or streaming sorted data.
3. After the doubling phase stops at index i, what range does binary search run on?
The last doubling step establishes that the target, if present, lies between i/2 and min(i, n-1).
Flash Cards
What does exponential search do first? — Doubles a probe index (1, 2, 4, 8, ...) until it brackets the target position.
What is the time complexity of exponential search? — O(log p), where p is the position of the target in the array.
What is exponential search most useful for? — Sorted arrays or streams of unknown or unbounded length.
What runs after the doubling phase finds a bracket? — Standard binary search, but only within that narrow bracket, not the whole array.