jsschools

Exponential Search

Finds a range where the target may exist by doubling the index, then performs binary search within that range; effective for unbounded or very large sorted arrays.

Spec ↗

Syntax

exponentialSearch(arr, target)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes A sorted array of numbers. Works on unbounded/infinite sorted sequences when combined with a bounds-checking wrapper.
target number Yes The value to find.

Returns

number — Index of target, or -1 if not found.

Examples

function binarySearch(arr, lo, hi, target) {
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

function exponentialSearch(arr, target) {
  if (arr[0] === target) return 0;
  let bound = 1;
  while (bound < arr.length && arr[bound] <= target) bound *= 2;
  return binarySearch(arr, bound >> 1, Math.min(bound, arr.length - 1), target);
}

const sorted = [2, 3, 4, 10, 40, 60, 80];
console.log(exponentialSearch(sorted, 10));
console.log(exponentialSearch(sorted, 5));
Output 
3
-1

// Effective when target is near the beginning
function exponentialSearch(arr, target) {
  if (arr[0] === target) return 0;
  let bound = 1;
  while (bound < arr.length && arr[bound] <= target) bound *= 2;
  let lo = bound >> 1, hi = Math.min(bound, arr.length - 1);
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] === target) return mid;
    arr[mid] < target ? (lo = mid + 1) : (hi = mid - 1);
  }
  return -1;
}

const large = Array.from({ length: 1000 }, (_, i) => i * 2);
console.log(exponentialSearch(large, 6)); // found at index 3
Output 
3

Notes

| Case | Time | Space | |---------|----------|-------| | Best | O(1) | O(1) | | Average | O(log i) | O(1) | | Worst | O(log n) | O(1) | where i is the index of the target. Exponential search is O(log i), which is faster than O(log n) binary search when the target is near the beginning of the array. It is particularly useful for unbounded sorted sequences where the length is unknown. The range-finding phase does O(log i) comparisons, and the subsequent binary search does another O(log i), so the total is still O(log i).

See also