# Exponential Backoff Search

# Exponential Backoff Search

Exponential backoff search finds a target in a sorted or monotone structure by expanding the search interval geometrically. Instead of scanning linearly, it probes positions at increasing distances until it either finds the target or bounds it inside an interval. A secondary search then refines the result.

This method is useful when the size of the data is unknown, unbounded, or expensive to traverse fully.

## Problem

Given a sorted sequence $A$ and a target $x$, find an index $i$ such that

$$
A[i] = x
$$

or determine that no such index exists.

The length of $A$ may be unknown or very large.

## Algorithm

Start from a small range. Double the range size until the target is less than or equal to the probed value. Then perform binary search inside the bounded interval.

```id="exb01"
exponential_backoff_search(A, x):
    if A[0] == x:
        return 0

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

    left = i // 2
    right = min(i, length(A) - 1)

    return binary_search(A, x, left, right)
```

## Example

Let

$$
A = [2, 4, 7, 10, 15, 21, 30, 45, 60]
$$

and

$$
x = 21
$$

Probing phase:

| step | index | value | relation |
| ---- | ----- | ----- | -------- |
| 1    | 1     | 4     | < x      |
| 2    | 2     | 7     | < x      |
| 3    | 4     | 15    | < x      |
| 4    | 8     | 60    | ≥ x      |

Now the target lies in the interval:

$$
[4, 8]
$$

Binary search in that range returns index $5$.

## Correctness

The exponential phase guarantees that once $A[i] \ge x$, the target must lie between $i/2$ and $i$ if it exists. This follows from monotonic ordering. The subsequent binary search operates on a valid interval that contains all possible positions of $x$.

## Complexity

Let $p$ be the position of the target.

| phase              | cost        |
| ------------------ | ----------- |
| exponential growth | $O(\log p)$ |
| binary search      | $O(\log p)$ |

Total time:

$$
O(\log p)
$$

Space complexity:

$$
O(1)
$$

## When to Use

Use exponential backoff search when:

* the sequence size is unknown
* the data is accessed through an interface like a stream or API
* random access exists but full length is unavailable
* the target is expected near the beginning

This method appears in systems that probe latency, retry policies, and unbounded logs, where doubling reduces the number of probes.

## Implementation

```id="exb02"
def exponential_backoff_search(a, x):
    if not a:
        return -1
    if a[0] == x:
        return 0

    i = 1
    n = len(a)

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

    left = i // 2
    right = min(i, n - 1)

    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            left = mid + 1
        else:
            right = mid - 1

    return -1
```

```id="exb03"
func ExponentialBackoffSearch(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
    }

    left := i / 2
    right := i
    if right >= n {
        right = n - 1
    }

    for left <= right {
        mid := (left + right) / 2
        if a[mid] == x {
            return mid
        } else if a[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}
```