Exponential Search

Exponential search finds a target in a sorted array by first locating a range where the target may lie, then applying binary search within that range.

It is effective when the position of the target is near the beginning or when the array size is unknown.

Problem

Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that

$$ A[i] = x $$

If no such index exists, return $-1$.

Key Idea

Instead of starting with the entire array, expand the search range exponentially:

• Check $A[1], A[2], A[4], A[8], \dots$
• Stop when exceeding the target or reaching array bounds

This identifies a range $[2^{k-1}, 2^k]$ that must contain the target if it exists.

Then apply binary search in that range.

Algorithm

exponential_search(A, x):
    if length(A) == 0:
        return -1

    if A[0] == x:
        return 0

    i = 1
    while i < length(A) and A[i] <= x:
        i = i * 2

    l = i // 2
    r = min(i, length(A) - 1)

    return binary_search(A, x, l, r)

Binary search on subarray:

binary_search(A, x, l, r):
    while l <= r:
        m = l + (r - l) // 2
        if A[m] == x:
            return m
        elif A[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

Example

Let

$$ A = [2, 4, 6, 8, 10, 12, 14, 16, 18] $$

and

$$ x = 10 $$

Range expansion:

step	i	A[i]
1	1	4
2	2	6
3	4	10

Now the target lies in $[2, 4]$. Binary search finds index $4$.

Correctness

The exponential phase guarantees that:

• The target lies between $i/2$ and $i$ if it exists
• The range is bounded and contains the target

Binary search then finds the exact position within that range.

Complexity

Let $i$ be the position of the target.

phase	cost
exponential growth	$O(\log i)$
binary search	$O(\log i)$
total	$O(\log i)$

Worst case:

$$ O(\log n) $$

Space:

$$ O(1) $$

When to Use

• When array size is unknown
• When accessing elements is expensive
• When target is likely near the beginning
• In unbounded or streaming contexts

Comparison

method	requirement	time
linear search	none	$O(n)$
binary search	sorted, known bounds	$O(\log n)$
exponential search	sorted	$O(\log i)$

Here $i$ is the position of the target.

Implementation

def exponential_search(a, x):
    n = len(a)
    if n == 0:
        return -1
    if a[0] == x:
        return 0

    i = 1
    while i < n and a[i] <= x:
        i *= 2

    l = i // 2
    r = min(i, n - 1)

    while l <= r:
        m = l + (r - l) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1

    return -1

func ExponentialSearch(a []int, x int) int {
    n := len(a)
    if n == 0 {
        return -1
    }
    if a[0] == x {
        return 0
    }

    i := 1
    for i < n && a[i] <= x {
        i *= 2
    }

    l := i / 2
    r := i
    if r >= n {
        r = n - 1
    }

    for l <= r {
        m := l + (r-l)/2
        if a[m] == x {
            return m
        } else if a[m] < x {
            l = m + 1
        } else {
            r = m - 1
        }
    }

    return -1
}