What is exponential search (exponential search)?

AlgorithmsJunior~3 min read

Short answer

Exponential search is an algorithm for searching a sorted array that first exponentially expands the working range (1, 2, 4, 8, ...) until it "jumps over" the target element, and then runs a binary search inside the found range. The running time is O(log i), where i is the position of the target element; in the worst case it is O(log n). It requires random access and sorted data.

Detailed breakdown

Idea of the algorithm

If the array is sorted in ascending order, we can quickly "estimate" the approximate range where the element might be. To do this, we check indices that grow exponentially: 1, 2, 4, 8, ... We stop when we meet an element that is not smaller than the target, or we go past the end of the array. After that, we run an ordinary binary search inside this range.

Steps of the algorithm

Check the first element: if it equals the target, return index 0.
Initialize bound = 1 and double it: 1, 2, 4, 8, … while bound < n and arr[bound] < target.
Determine the bounds for binary search: left = bound / 2 (rounded down), right = min(bound, n - 1).
Run binary search on [left, right]. Find the index, or return -1 if the element is not there.

Complexity

Time: O(log i), where i is the index of the target; O(log n) in the worst case. The exponential stage is O(log i), the binary stage is O(log i).
Memory: O(1) extra memory.

When to use it

Sorted arrays with fast random access (for example, ordinary in-memory arrays).
Structures where the length is not known in advance or is logically "unbounded" (for example, access interfaces that return a value by index but do not expose a size; this often comes up in interview problems).
Scenarios where the target is expected to be "close to the start" - exponential growth quickly localizes a small range.

Advantages and limitations

Pros: localizes the range faster than linear search; does not require knowing the array length; theoretically can be more efficient than an ordinary binary search if the target is close to the start (a smaller logarithm of i, rather than of n).
Cons: requires sorted data and random access; not applicable on structures with expensive indexed access (for example, linked lists); with multiple duplicates it returns an arbitrary index unless the binary stage is modified to find the left boundary.

Code example (JavaScript)

function exponentialSearch(arr, target) {
  const n = arr.length;
  if (n === 0) return -1;
  if (arr[0] === target) return 0;

  // Exponential expansion of the range
  let bound = 1;
  while (bound < n && arr[bound] < target) {
    bound *= 2;
  }

  const left = Math.floor(bound / 2);
  const right = Math.min(bound, n - 1);
  return binarySearchInRange(arr, target, left, right);
}

function binarySearchInRange(arr, target, left, right) {
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] === target) return mid; // See the variant below for the first position
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// Variant that returns the index of the FIRST occurrence with duplicates
function binarySearchFirst(arr, target, left, right) {
  let ans = -1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] >= target) {
      if (arr[mid] === target) ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
}

// Usage example:
// const idx = exponentialSearch([1,3,5,7,9,12,15,18,21], 12); // => 5

Step-by-step example

Array: [1, 3, 5, 7, 9, 12, 15, 18, 21, 24, 27, 30], target: 18.

Check arr[0] = 1 ≠ 18.
bound = 1: arr[1] = 3 < 18 → bound = 2.
bound = 2: arr[2] = 5 < 18 → bound = 4.
bound = 4: arr[4] = 9 < 18 → bound = 8.
bound = 8: arr[8] = 21 ≥ 18 → range found: [left = 4, right = 8].
Binary search on [4, 8]: mid = 6 → arr[6] = 15 < 18 → left = 7; mid = 7 → arr[7] = 18 → found, index 7.

Variations and practical tips

For arrays with duplicates, use binary search for the left/right boundary to return the first/last occurrence.
If the order is descending, invert the comparisons in both stages.
With an unknown collection size, use safe access that handles going out of bounds (for example, an API might return +∞/undefined when accessed past the end). Keep doubling bound until you hit the "signal" of going out of bounds, then run binary search on the last valid range.

Checking edge cases

Empty array → return -1.
Target smaller than the first element → the binary stage runs on the narrow range [0, 0].
Target larger than all elements → right will be n - 1; the binary stage correctly returns -1.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.