Exponential Search from Scratch (2026)
Exponential search (also called doubling search or galloping search) is a hybrid algorithm that combines exponential probing with binary search. It is particularly useful for unbounded arrays or when the target is near the beginning of the array. The algorithm first finds a range by doubling the index, then performs binary search within that range. It runs in O(log n) time.
In this tutorial, we will implement exponential search, analyze its advantages over binary search for unbounded data, explore its use in infinite sorted arrays, and understand its connection to interpolation search and jump search.
Exponential Search Algorithm
Exponential search works in two phases. First, it finds a range [2^0, 2^1, 2^2, ...] where the target might be, by starting at index 1 and doubling until we find an element greater than the target or reach the end. The range [2^(k-1), min(2^k, n)] is guaranteed to contain the target if it exists. Second, we perform binary search within this range.
The first phase takes O(log p) steps where p is the position of the target. The second phase takes O(log range) = O(log min(p, n)) steps. Total complexity is O(log n).
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
low = index // 2
high = min(index, n - 1)
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: low = mid + 1
else: high = mid - 1
return -1
arr = [2, 3, 4, 10, 40, 50, 60, 70, 80, 90, 100]
print(exponential_search(arr, 10)) # 3Unbounded Array Search
Exponential search shines when searching in unbounded or infinite sorted arrays where we don't know the size. We can probe exponentially (1, 2, 4, 8, ...) until we find an element greater than the target. This makes it ideal for searching in streaming data, where data arrives continuously and the array size is unknown.
Since we don't know the array size, we cannot use standard binary search. Exponential search solves this by first finding an upper bound using doubling, then applying binary search.
#include
using namespace std;
int exponentialSearchUnbounded(int get(int), int target) {
if (get(0) == target) return 0;
int index = 1;
while (true) {
int val = get(index);
if (val == target) return index;
if (val > target) break;
index *= 2;
}
int low = index / 2, high = index;
while (low <= high) {
int mid = low + (high - low) / 2;
int val = get(mid);
if (val == target) return mid;
else if (val < target) low = mid + 1;
else high = mid - 1;
}
return -1;
} Exponential Search vs Other Searches
Exponential search is superior to binary search when the target is likely near the beginning of the array, as it starts probing from index 1 and can find the range quickly. For uniformly distributed data, interpolation search (O(log log n) average) may be faster. For unknown-size data, exponential search is the only viable option among comparison-based searches.
The time complexities are: Linear O(n), Binary O(log n), Exponential O(log n) but better constant for early elements, Interpolation O(log log n) average for uniform data, Jump Search O(sqrt(n)).
import bisect, time, random
def linear_search(arr, t):
for i, v in enumerate(arr):
if v == t: return i
return -1
def exponential_search(arr, t):
if not arr or arr[0] == t: return 0 if arr else -1
idx = 1
while idx < len(arr) and arr[idx] <= t: idx *= 2
lo, hi = idx // 2, min(idx, len(arr) - 1)
i = bisect.bisect_left(arr, t, lo, hi + 1)
return i if i <= hi and arr[i] == t else -1
def jump_search(arr, t):
n = len(arr)
step = int(n ** 0.5)
prev = 0
while arr[min(step, n) - 1] < t:
prev = step
step += int(n ** 0.5)
if prev >= n: return -1
for i in range(prev, min(step + 1, n)):
if arr[i] == t: return i
return -1Applications and Variants
Exponential search is used in galloping mode during merge sort to efficiently find insertion positions. It is the basis for searching in dynamic arrays where elements are appended. In databases, it helps in range queries on sorted indexes. The galloping search variant is used in Timsort (Python and Java's sorting algorithm).
Variants include interpolation-exponential search (combining interpolation for better initial range estimation) and Fibonacci search (using Fibonacci numbers instead of powers of 2 for the range finding phase).
public class ExponentialSearch {
static int gallopingSearch(int[] arr, int target) {
if (arr.length == 0) return 0;
if (arr[0] >= target) return 0;
int bound = 1;
while (bound < arr.length && arr[bound] < target) bound *= 2;
int low = bound / 2, high = Math.min(bound, arr.length - 1);
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low;
}
static int countInRange(int[] arr, int lo, int hi) {
return gallopingSearch(arr, hi + 1) - gallopingSearch(arr, lo);
}
}Frequently Asked Questions
When to use exponential search?
Use exponential search when the array size is unknown (unbounded), when the target is likely near the beginning, or when you need to search in streaming data. It is also used as a subroutine in galloping merge sort.
What is the time complexity?
Exponential search has O(log n) worst case, same as binary search. However, it performs better when the target is near the beginning: O(log p) where p is the target's position.
How does exponential search work on infinite arrays?
It probes indices 1, 2, 4, 8, ... until finding a value >= target or exceeding the array. This takes O(log p) steps. Then binary search in the found range takes O(log p) steps.
What is galloping search?
Galloping search is another name for exponential search. It is used in merge sort's galloping mode to skip large chunks of elements when merging sorted sequences, improving merge sort's performance.
Originally published on Ayodhyyya. Last updated June 1, 2026.