Algorithm Guidecomplexity: O(log n)

Exponential Search

Expands the index by powers of two (1, 2, 4, 8, …) to bracket the range containing the target quickly, then runs a binary search within it. It's strong for searching unbounded or infinite streams of unknown length.

01Exponential Search

Explore How It Works

Starting exponential search. Probe one slot ahead, then two, then four — doubling until the target's range is found — and binary-search inside it.

The first probe, 12, is still below 45. Double the distance.

Two slots on, 23 also falls short of 45. Double again.

Four slots on, the value is 45 — equal to the target, but the rule says probe once more.

Eight slots on, 89 overshoots 45. The target lies in the range we just passed over.

Binary-search the narrowed range. The middle value, 67, is larger than 45, so the back half is dropped.

The middle of what remains is 45 — a match.

Search complete · 45 sits at index 4. Even with an array of unknown length, probing the front is enough to bound the range.

Live Python

# target: 45

1def exponential_search(arr, target):

2 if arr[0] == target:

# i: 1

3 return 0

4 i = 1

5 while i < len(arr) and arr[i] <= target:

6 i *= 2

7 return binary_search(arr, target,

8 i // 2, min(i, len(arr) - 1))

9def binary_search(arr, target, low, high):

10 while low <= high:

11 mid = (low + high) // 2

12 if arr[mid] == target:

13 return mid

14 elif arr[mid] < target:

15 low = mid + 1

16 else:

17 high = mid - 1

18 return -1

1 / 8

02 Understand It Simply

For Everyone

🔑How It Works

Doubles the stride — 1, 2, 4, 8 — to bracket the range, then binary searches inside it. Used when the size is unknown.

💡In Plain Words

Doubles the index to pinpoint the range that holds the target, then binary-searches within it.

Strong for data of unknown length.

📍Where It's Used

–Infinite/unbounded streams
–sorted data of unknown length

03 Python Implementation

A clean, readable reference implementation of the core logic of Exponential Search.

core_implementation.py

def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    i = 1
    while i < len(arr) and arr[i] <= target:
        i *= 2
    return binary_search(arr, target,
                         i // 2, min(i, len(arr) - 1))