Exponential Search answers a clever question: how far should we even look? It checks the first element, then doubles the search bound — 1, 2, 4, 8 — until a bound exceeds the target. Only then does it run a Binary Search inside that narrow range.

Also called galloping search, it shines when the target likely sits near the beginning of a (possibly unbounded) sorted sequence.

How It Works

1. Check index 0 first — the best case.
2. Set bound = 1 and keep doubling while arr[bound] < target (and bound is in range).
3. The target, if present, now lies between bound/2 and min(bound, n-1).
4. Run a Binary Search inside that range; return the index or -1.

Key Insight

The doubling is a self-sizing guess: it finds the smallest power-of-two bound that contains the target, so the subsequent binary search range has size at most bound, giving O(log bound). Since the doubling itself is also O(log bound) — and bound ≤ 2·target_position — the whole search is O(log n), the same as plain binary search, but with a big practical win: when the target is near the front, exponential search examines far fewer elements. For an unbounded (or unknown-length) sorted stream, exponential search is the only standard technique — you can’t binary search a range you haven’t bounded yet.

Worked Example

Search for 8 in [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]:

• Index 0: 1 ≠ 8 → continue
• bound=1: arr[1]=2 < 8 → double
• bound=2: arr[2]=3 < 8 → double
• bound=4: arr[4]=8 ≥ 8 → stop
• Binary search in [2, 4]: mid=3 → 5 < 8 → search [4, 4] → 8 = 8 → return 4

Search for 88: bounds grow to 8, binary search in [4, 8] covers [8, 13, 21, 34, 55] with no match → return -1. In the visualizer, the “bound” marker doubles before the binary-search highlight narrows in.

Edge Cases & Pitfalls

• Empty array — return -1 before any doubling.
• Target at index 0 — handled by the first check: best case O(1).
• Target beyond array end — the doubling clamps to n; the binary search over the tail misses.
• bound overflow — doubling past array bounds must clamp to n-1 (or n) to avoid index errors.
• Duplicates — returns some occurrence within the range: use lower-bound variants if you need the first.

Comparison With Other Searches

Applications

• Searching unbounded/infinite sorted sequences or streams where the length is unknown
• Front-loaded data — sorted logs, newsfeeds, or leaderboards where recent (early) entries are the likeliest targets
• Hybrid start for interpolation-style searches (bound first, then binary)

Practice Trajectory

1. Hand-trace Exponential Search for target 21 in [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22], noting each doubling.
2. Explain why you can’t binary search an unknown-length array without first bounding it.
3. Show the range [bound/2, bound] always contains the target if it exists.
4. Compare the element count visited for a target at index 0 across exponential and binary search.
5. Implement exponential search over an infinite generator (no length) and confirm it terminates.