Exponential Search

1. One-Liner

Exponential search (also called doubling search) finds a sorted target by probing indices 1, 2, 4, 8, … until the value is bracketed, then runs binary search in that range.

2. The Problem It Solves

When the array is sorted but length is unknown or you want O(log i) behavior where i is the index of the answer (unbounded/infinite list metaphor), pure binary search on [0, n-1] is not applicable without knowing n.

3. The Core Idea

Zoom out exponentially until you pass the target (or hit the end), then zoom in with binary search on the last doubled interval. Like climbing stairs two steps at a time until you overshoot, then fine-tuning.

4. How It Works (Step-by-Step)

Step	Action
1	If first element is target, return 0.
2	Set `bound = 1`; while `bound < n` and `arr[bound] < target`, `bound *= 2`.
3	Binary search between `bound/2` and `min(bound, n-1)`.

5. Dry Run Example

Array: [1,2,3,5,8,13,21,34], target: 13.

Phase	bound	arr[bound]	Action
Double	1	2	< 13 → continue
Double	2	3	< 13
Double	4	13	≥ 13 → binary on [2, 4]

Binary finds index 5 (0-based: actually indices: bound/2=2 to min(4,7)=4 — arr[4]=13 → found).

6. Key Properties

Property	Detail
Time	O(log i) if target at index `i`; O(log n) overall for finite `n`.
Use	Unbounded search patterns; also first ≥ x style ranges.

7. Where It Is Used

Company / domain	Use
Streaming / logs	Find first record ≥ timestamp without full size.
Systems	Bounded binary after coarse localization.

8. Interview Tips

Explain why double: bracket in logarithmic number of outward steps. Combine with binary for the inner phase. Watch off-by-one on bounds.

9. Comparison with Other Algorithms

Algorithm	Note
Binary	Needs known hi upfront.
Exponential	Finds hi adaptively.
Jump	Fixed √n stride, not doubling.

10. Complexity

Time	Space
O(log i) locate + O(log i) binary	O(1) iterative

Implementation Example (PYTHON)

def exponential_search(arr, target):
    n = len(arr)
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    bound = 1
    while bound < n and arr[bound] < target:
        bound *= 2
    lo = bound // 2
    hi = min(bound, n - 1)
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1