1. Empty input
Empty arrays cannot contain the target.
if (arr.length === 0) return -1Typorithm · medium
Exponential Search
▷ Interactive algorithm labexponential-searchsearchsorted-arrayrange-findingbinary-search
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Exponential Search
Search Algorithms
Exponential Search first finds a likely sorted range by doubling, then runs Binary Search inside that range.
Exponential Search works on sorted arrays.
It quickly expands the right boundary by powers of two.
Once the boundary reaches or passes target, the target can only be in the previous-to-current window.
The final phase is ordinary Binary Search inside that window.
Preparing algorithm lab…
01
Check empty and first item.
02
Double bound while values are too small.
03
Search between previous bound and current bound.
04
Uses Binary Search after range finding.
05
Time is O(log n).
function exponentialSearch(arr, target) {
if (arr.length === 0) return -1;
if (arr[0] === target) return 0;
let bound = 1;
while (bound < arr.length && arr[bound] < target) {
bound *= 2;
}
let left = Math.floor(bound / 2);
let right = Math.min(bound, arr.length - 1);
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Read the implementation
Connect each part of the code to the concept before you type.
2. First item
Check index 0 before doubling from bound 1.
if (arr[0] === target) return 03. Initial bound
Start with a small right bound and grow exponentially.
let bound = 14. Double bound
Double until the bound passes target or the array ends.
bound *= 25. Left bound
The target, if present, must be after the previous bound.
let left = Math.floor(bound / 2)6. Right bound
Clamp the right boundary to the last valid index.
let right = Math.min(bound, arr.length - 1)7. Binary phase
After finding a window, use Binary Search inside it.
const mid = Math.floor((left + right) / 2)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.