Exponential Search first finds a range [2^k, 2^(k+1)] where the target lies by doubling the index until an element greater than the target is found. It then performs Binary Search in that range. It is especially useful for unbounded or infinite sorted arrays and achieves O(log n) time.
int exponentialSearch(vector<int>& arr, int target) {
int n = arr.size();
if (arr[0] == target) return 0;
int i = 1;
while (i < n && arr[i] <= target) i *= 2;
int lo = i/2, hi = min(i, n-1);
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (arr[mid]==target) return mid;
if (arr[mid]<target) lo=mid+1; else hi=mid-1;
}
return -1;
}The algorithm doubles the index (1,2,4,8,16...) until it finds an index where the element exceeds the target. This takes O(log n) steps and identifies a range of size O(n/2^k) containing the target.
Once the range [i/2, i] is found, Binary Search is applied within it. Because the range size is at most 2^(log n) = n, Binary Search within it is also O(log n).
Exponential Search is ideal for unbounded or infinite sorted sequences where you do not know the length in advance. It finds the search range adaptively without needing n.
Quiz coming soon for this algorithm.