Exponential Search

Exponential search answers a question binary search can't: *how do you search a sorted list when you don't know how long it is?* It works in two moves — first it finds a small window where the target must live by doubling an index bound, then it binary-searches just that window. Because it homes in before searching, the cost scales with where the target *is*, not how big the list could be.

Phase 1 — double until you overshoot

Start with a bound at index 1. Keep doubling it — 1, 2, 4, 8, 16… — checking the value at each bound. The instant a bound's value exceeds the target (or runs off a known end), stop. The target, if present, lies between the last bound that was too small and the first that was too big.

Phase 2 — binary-search the window

That window spans from roughly bound/2 to bound. Run an ordinary binary search on just that slice. Since the window's size is about the same as the bound itself, finishing it off costs another log of that range.

function exponentialSearch(arr, target) {
  if (arr[0] === target) return 0;
  let bound = 1;
  // double until we pass the target or the end
  while (bound < arr.length && arr[bound] < target) {
    bound *= 2;
  }
  // binary-search the window [bound/2, min(bound, n-1)]
  let lo = Math.floor(bound / 2);
  let hi = Math.min(bound, arr.length - 1);
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}