Exponential search

O(log n)

Exponential search finds a range containing the target by doubling an index (1, 2, 4, 8, …) until the value exceeds the target, then runs a binary search within that range. It is handy for unbounded or very large sorted inputs where you don't know the size up front. O(log n).

Array
Edit the input and press Play

How it works

  1. Check index 0, then double the index (1, 2, 4, …) until its value passes the target.
  2. That gives a range [bound/2, bound] that must contain the target if present.
  3. Binary-search that range.
  4. Report the index if found, otherwise that the value is absent.

Pseudocode

1exponentialSearch(a, target):       # O(log n) — a is sorted2  if a[0] = target: return 03  bound ← 14  while bound < n and a[bound] ≤ target:5    bound ← bound * 26  binarySearch(a, target, bound/2, min(bound, n-1))