Exponential Search

Binary search needs both a lower and an upper bound up front. When an array is effectively unbounded — a stream, a very large lazily evaluated sequence, or an array whose length is unknown — you cannot set hi = arr.length - 1 before you start. Exponential search solves this by discovering the window first.

The Two Phases

Phase 1 — Doubling: Start with bound = 1 and keep doubling until arr[bound] >= target or you exceed the array length. This takes O(log i) steps where i is the index of the target.

Phase 2 — Binary search: Run binary search on the window [bound / 2, min(bound, arr.length - 1)]. The target must lie here because arr[bound / 2] < target <= arr[bound] (invariant from the doubling phase).

Implementation

function binarySearch(arr, target, lo, hi) {
  while (lo <= hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);
    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.length === 0) return -1;
  if (arr[0] === target) return 0;

  // Phase 1: find upper bound by doubling
  let bound = 1;
  while (bound < arr.length && arr[bound] < target) {
    bound *= 2;
  }

  // Phase 2: binary search in [bound/2, min(bound, n-1)]
  const lo = Math.floor(bound / 2);
  const hi = Math.min(bound, arr.length - 1);
  return binarySearch(arr, target, lo, hi);
}

const arr = [1, 2, 4, 8, 16, 32, 64, 128, 256];
exponentialSearch(arr, 32);  // 5
exponentialSearch(arr, 50);  // -1

Complexity

i is the index of the target in the array. For targets near the beginning the algorithm is extremely fast — O(log 1) = O(1) for the very first element.

Invariants

During the doubling phase, arr[bound / 2] < target holds for every doubled value of bound except possibly the last. This guarantees the search window passed to binary search is valid: the target cannot be to the left of bound / 2.

When to Use It

• Unknown array length — e.g. a file with binary-searchable records and no header giving the count.
• Very large sorted arrays — when the target is likely to be near the beginning, exponential search arrives faster than starting binary search from [0, n-1].
• Infinite sorted streams — model the stream as an array indexed by a counter; the doubling phase probes the stream until it finds a bracket.

Up Next

Ternary search applies a similar divide-and-conquer idea to finding the minimum or maximum of a unimodal function rather than a specific value.