Exponential Search
Exponential Search first finds a range where the target may exist by doubling the index (1, 2, 4, 8…), then runs Binary Search within that range. Especially useful for unbounded or infinite-length sorted arrays.
Search Target
↑ Set a target value above to begin searching the array
Legend
- • Orange phase — exponential doubling
- • Violet phase — binary search in range
- • Footer label shows current phase
Inspector
Legend
- • Orange phase — exponential doubling
- • Violet phase — binary search in range
- • Footer label shows current phase
Inspector
Reference implementation of Exponential Search. Select a language tab to view and copy the code.
#include <math.h>
/* Binary search helper within [low, high] */
int binary_search(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int exponential_search(int arr[], int n, int target) {
if (arr[0] == target) return 0;
int bound = 1;
while (bound < n && arr[bound] <= target)
bound *= 2;
int low = bound / 2;
int high = (bound < n) ? bound : n - 1;
return binary_search(arr, low, high, target);
}#include <vector>
#include <algorithm>
int exponentialSearch(const std::vector<int>& arr, int target) {
int n = static_cast<int>(arr.size());
if (arr[0] == target) return 0;
int bound = 1;
while (bound < n && arr[bound] <= target)
bound *= 2;
int low = bound / 2;
int high = std::min(bound, n - 1);
// Binary search in [low, high]
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}public static int exponentialSearch(int[] arr, int target) {
int n = arr.length;
if (arr[0] == target) return 0;
int bound = 1;
while (bound < n && arr[bound] <= target)
bound *= 2;
int low = bound / 2;
int high = Math.min(bound, n - 1);
// Binary search in [low, high]
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}def exponential_search(arr: list[int], target: int) -> int:
n = len(arr)
if arr[0] == target:
return 0
# Phase 1: find the range [bound/2, bound]
bound = 1
while bound < n and arr[bound] <= target:
bound *= 2
low = bound // 2
high = min(bound, n - 1)
# Phase 2: binary search within [low, high]
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 -1function exponentialSearch(arr, target) {
const n = arr.length;
if (arr[0] === target) return 0;
// Phase 1: find range [bound/2, bound]
let bound = 1;
while (bound < n && arr[bound] <= target)
bound *= 2;
let low = bound >> 1; // bound / 2
let high = Math.min(bound, n - 1);
// Phase 2: binary search within [low, high]
while (low <= high) {
const mid = low + Math.floor((high - low) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Python — Code Walkthrough
Phase 1 comment — range discovery
# Phase 1: find the range [bound/2, bound]bound starts at 1 and doubles each step. After the loop, we know target (if present) sits in the half-open interval [bound//2, min(bound, n−1)].
Floor division for low
low = bound // 2Python's // operator gives integer floor division. bound is always a power of 2 after the doubling loop, so bound // 2 equals the previous power of 2 — the left boundary of our range.
min() for safe high
high = min(bound, n - 1)Python built-in min clamps bound to n−1. No import needed. This prevents an IndexError when bound overshoots the list length.
Phase 2 — binary search with floor division
mid = low + (high - low) // 2Python integers don't overflow, but using // keeps mid an integer. The same overflow-safe form as other languages is used as a best-practice habit.