Exponential Search

Exponential search finds a target in a sorted array by first growing a probe index in powers of two — 1, 2, 4, 8, 16, … — until it overshoots the target, then binary-searching the small window it just bracketed. The doubling phase locates a range in O(log i) steps (where i is the target's index), and the binary search finishes inside that range, also in O(log i).

The headline use case: a sorted but unbounded stream where you do not know n up front — an API that returns a[k] on demand, or an array so large that reading its length is expensive. Plain binary search needs hi = n - 1 to start; exponential search discovers a usable upper bound on its own.

Intuition

Imagine reading a sorted list one reach at a time, but you have no idea how long it is. You cannot start binary search because you do not know where the right edge is. So you guess an edge cheaply: look 1 step ahead, then 2, then 4, then 8 — each guess twice as far as the last. The moment a probe lands on a value bigger than your target, you know the target is somewhere between your previous probe and this one. Because each probe doubled, you reach any index i in only about log2(i) probes.

That bracket (i/2, i] is never wider than the distance you already traveled, so the follow-up binary search is just as cheap. Doubling to find the range, then halving to pinpoint inside it — two logarithmic phases back to back.

Walk through it

Step through the animation on the right. The top i pointer is the doubling probe; the bottom lo / mid / hi pointers run the binary search.

First we check a[0] — a quick special case, since the probe starts at i = 1. Then the probe marches: i = 1 (value 3), i = 2 (value 5), i = 4 (value 12), i = 8 (value 34) — every one is still at or below the target 34, so i keeps doubling. The next double sends i to 16, which is past the end of the 10-element array, so the loop stops and clamps the right edge. The window is now indices (8, 9], i.e. lo = 8, hi = 9.

Phase 2 binary-searches that two-cell window: mid = 8, and a[8] = 34 matches the target — found at index 8. Notice how little of the array the binary search actually touched: the doubling phase did the heavy lifting of locating where to look.

The code, line by line

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

• Lines 3–4 handle a[0] directly, because the probe starts at index 1 — without this, the i // 2 bracket could never include index 0.
• Line 5 seeds the probe at i = 1; the loop on line 6 doubles it while a[i] has not yet passed the target. The i < n guard stops the probe from reading off the end.
• Line 7 is the doubling step — i *= 2 turns the index into 1, 2, 4, 8, …, which is why the probe phase is logarithmic.
• Line 8 hands the bracket to binary search: lo = i // 2 (the last probe that was still in range) and hi = min(i, n - 1) (clamped in case the probe overshot the array).
• Lines 11–18 are a textbook binary search over just that window: test the midpoint, return on a match, and otherwise discard the half that cannot contain the target.

Complexity

The cost is driven by i, the target's index, not by n. If the target sits near the front of a billion-element array, exponential search touches only a handful of cells — O(log i) — whereas plain binary search would still start from the middle of the whole array. When the target is near the end, i approaches n and the cost matches binary search, so you never pay more than O(log n) asymptotically.

When to use / pitfalls

Practice