Exponential Search Visualizer

Target:

Speed:

SlowFast

Elements:

715

(10)

Current Bound

Boundaries

Target Value

Found

Other

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(log n) - finds range in O(log n) then binary search

Space Complexity: O(1) - uses constant extra space

Best Case: O(1) - target is the first element

Worst Case: O(log n) - target is at the end or not found

Prerequisite: Array must be sorted in ascending order

How it works: First finds a range where target might exist by exponentially increasing the bound (1, 2, 4, 8, ...), then performs binary search within that range.

When to use: When you don't know the size of the array or when the target is likely to be near the beginning.

Implementation

function exponentialSearch(arr, target) {
  if (arr.length === 0) return -1;
  if (arr[0] === target) return 0;
  let bound = 1;
  while (bound < arr.length && arr[bound] <= target) {
    bound *= 2;
  }
  return binarySearch(
    arr,
    target,
    Math.floor(bound / 2),
    Math.min(bound, arr.length - 1)
  );
}
function binarySearch(arr, target, left, right) {
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}