Exponential & Interpolation Search

Imagine you're looking for a house on a street, but you don't know how long the street is. You start by taking 1 step, then 2 steps, then 4, then 8 — doubling your step size each time — until you overshoot your destination. Now you know the house is somewhere in the last stretch you crossed. You go back to where you started that stretch and do a careful room-by-room search.

That's exponential search. Phase one: double until you overshoot. Phase two: binary search the range you've narrowed down.

Why not just use binary search?

Binary search is perfect when you know the array's size. But sometimes you don't — imagine a stream of sorted data coming in, or an API that lets you access any index but won't tell you how many elements there are. You can't set hi = n - 1 if you don't know n.

Exponential search solves this: it discovers the range by doubling, then searches it. Even better — if your target happens to be near the beginning (say, at position p), you find it in \(O(\log p)\) time, regardless of how enormous the full array is. Binary search would need \(O(\log n)\) where n >> p.

The two phases

Phase 1 — Bounding: Start at index 1. If arr[1] < target, jump to index 2, then 4, then 8, doubling each time. Stop when you find arr[i] >= target or you fall off the end of the array. The target must be in the range [i/2, i].

Phase 2 — Binary search: Run standard binary search on [i/2, min(i, n-1)]. Since this range has size at most i/2 which is at most the target's position, the binary search costs \(O(\log p)\).

Total cost: \(O(\log p)\) for bounding + \(O(\log p)\) for binary search = \(O(\log p)\). For a random target, p ≈ n/2 on average, so this is \(O(\log n)\).

Exponential Search

def binary_search(arr, lo, hi, target):
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def exponential_search(arr, target):
    n = len(arr)
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    # Double the range until we overshoot
    i = 1
    while i < n and arr[i] < target:
        i *= 2
    # Binary search in the bounded range
    return binary_search(arr, i // 2, min(i, n - 1), target)

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
print(exponential_search(arr, 7))   # 3
print(exponential_search(arr, 10))  # -1

Output

3
-1

Complexity

🚀 Bounding phasep = target's index; only takes log p doublings to overshoot

Log of target position\(O(\log p)\)

🔍 Binary search phaseThe bounded range has size ≈ p, so binary search costs \(O(\log p)\)

Log of bounded range\(O(\log p)\)

⚡ TotalBoth phases combined; \(O(\log p)\) ≤ \(O(\log n)\)

Logarithmic in target position\(O(\log n)\)

💾 SpaceOnly a few index variables — no extra memory

Constant\(O(1)\)

Why not just use binary search?

The two phases

Exponential Search

Complexity

Quick check