# Exponential Search, Explained Step by Step

> Double a bound until it passes the key, then binary search that range.

Searching algorithm. Interactive version, with a step-by-step visualizer of a real recorded run: https://www.tmread.me/algorithms/exponential-search

## Complexity

| | Big-O | Why |
|---|---|---|
| Best time | O(1) | The key is the first value. |
| Average time | O(log n) | About log i doublings, then a binary search over about i values (i = the key’s position). |
| Worst time | O(log n) | Never worse than binary search, and faster when the key is near the start. |
| Extra space | O(1) | A bound and two pointers. |

## What is exponential search?

Exponential search finds a key in a sorted list in two phases. First it finds a range that must contain the key, by doubling a bound: 1, 2, 4, 8, 16… until the value at the bound is at least the key. Then it runs binary search inside that range.

Why not just use binary search? Because exponential search is fast when the key is near the start, and it works even when you don’t know how long the list is. It is also called doubling search or galloping search.

## How it works, step by step

Press play above. In the first phase, the blue bar is the bound being tested against the key; watch it double. Then `lo` and `hi` appear around the range, everything outside fades out, and a normal binary search finishes the job.

1. Check the first value. If it is the key, return 0.
2. Set the bound `b = 1`.
3. While `b` is inside the list and `a[b]` is smaller than the key, double it: `b *= 2`.
4. Now the key, if it is there, sits between `b // 2` and `b` (or the end of the list, whichever comes first).
5. Binary search that range: `lo = b // 2`, `hi = min(b, n − 1)`.

The doubling phase stops at the first bound that reaches the key. The previous bound, half as big, was still too small, so the key is in between.

## Time and space complexity

Let `i` be the key’s position. The doubling phase takes about `log₂ i` steps to pass it. The range it finds has about `i/2` values, so the binary search takes about `log₂ i` more. The total is O(log i).

That is the key idea: the cost depends on where the key is, not on how long the list is. A key at position 10 in a list of a billion takes about the same time as in a list of 20.

Best case, O(1): the key is the first value. Worst case, O(log n): the key is near the end, so `i` is close to `n`. That makes exponential search never worse than binary search by more than a small constant.

Space is O(1) with a loop-based binary search.

## Common mistakes

- Doubling past the end of the list. Check `b < len(a)` before reading `a[b]`, and clamp `hi` to `n − 1`.
- Starting the bound at 0. Doubling 0 stays 0 forever. Check index 0 on its own, then start at 1.
- Searching from 0 to `b` instead of `b // 2` to `b`. It still works, but throws away the doubling phase’s work.
- Using it on unsorted data. Like binary search, it relies on sorted order.

## When to use it

- Unbounded or unknown-length data: a stream, or an API that returns “out of range” instead of a length.
- When the key is likely near the start, like looking up recent entries in a sorted log.
- Merging sorted lists. Timsort, Python’s built-in sort, uses this “galloping” trick to skip over long runs quickly when merging.

For a plain sorted array where the key could be anywhere, binary search is just as good and a little simpler.

## Code

### Python

```python
def exponential_search(a, key):
    if a[0] == key: return 0
    b = 1
    while b<len(a) and a[b]<key: b*=2
    lo, hi = b//2, min(b, len(a)-1)
    while lo <= hi:
        mid = (lo+hi)//2
        if a[mid] == key: return mid
        if a[mid] < key: lo = mid+1
        else: hi = mid-1
    return -1
```

### TypeScript

```ts
function exponentialSearch(a: number[], key: number) {
  if (a[0] === key) return 0;
  let b = 1;
  while (b < a.length && a[b] < key) b *= 2;
  let lo = Math.floor(b / 2);
  let hi = Math.min(b, a.length - 1);
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (a[mid] === key) return mid;
    if (a[mid] < key) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
```

### Go

```go
func exponentialSearch(a []int, key int) int {
    if a[0] == key {
        return 0
    }
    b := 1
    for b < len(a) && a[b] < key {
        b *= 2
    }
    lo, hi := b/2, min(b, len(a)-1)
    for lo <= hi {
        mid := (lo + hi) / 2
        if a[mid] == key {
            return mid
        }
        if a[mid] < key {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}
```

## Questions

### Why is it called exponential search?

The bound grows exponentially: 1, 2, 4, 8, 16, doubling each step.

### Is exponential search faster than binary search?

When the key is near the start, yes: O(log i) instead of O(log n). Otherwise they are about the same.

### Can exponential search work on an infinite list?

Yes, as long as it is sorted. The doubling phase finds a finite range around the key without ever needing the length.

## Related algorithms

- [Binary Search](https://www.tmread.me/algorithms/binary-search.md): Check the middle of a sorted array and throw away the half that can’t hold the key.
- [Jump Search](https://www.tmread.me/algorithms/jump-search.md): Jump ahead √n at a time, then walk back through one block.
- [Interpolation Search](https://www.tmread.me/algorithms/interpolation-search.md): Guess where the key should be from its value, like opening a dictionary near the right letter.

---

From The Missing README (computer science, made visible). Want to run your own code and watch every step? Join Cohort 0, the early-access group: https://www.tmread.me/#cohort