# Exponential Search

# 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

```id="exp-srch"
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:

```id="exp-bin"
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

```id="py-exp"
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
```

```id="go-exp"
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
}
```