# Interpolation Search, Explained Step by Step

> Guess where the key should be from its value, like opening a dictionary near the right letter.

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

## Complexity

| | Big-O | Why |
|---|---|---|
| Best time | O(1) | The first guess lands on the key. |
| Average time | O(log log n) | On evenly spread values, each guess shrinks the range dramatically. |
| Worst time | O(n) | On skewed values the guesses creep forward one step at a time. |
| Extra space | O(1) | Two pointers and a probe. |

## What is interpolation search?

Interpolation search finds a key in a sorted list by guessing where it should be, based on its value. Binary search always checks the middle. Interpolation search checks where the key would sit if the values were spread out evenly.

You already do this. Looking up “Williams” in a phone book, you don’t open it in the middle. You open it near the end, because W is near the end of the alphabet. Looking up “Baker”, you open it near the front.

When values are spread evenly, this is incredibly fast. When they are not, it can be slow. The demo lets you see both sides of that.

## How it works, step by step

Press play above. `lo` and `hi` mark the range that can still hold the key, and the bars outside it fade out. The blue bar is the probe: the position the formula guessed.

1. Set `lo = 0` and `hi` to the last index.
2. Check that the key is between `a[lo]` and `a[hi]`. If it isn’t, it can’t be in the list.
3. Guess a position: `probe = lo + (key − a[lo]) × (hi − lo) / (a[hi] − a[lo])`. This asks: what fraction of the way from `a[lo]` to `a[hi]` is the key? Then go that fraction of the way from `lo` to `hi`.
4. If `a[probe]` is the key, return it.
5. If `a[probe]` is smaller, move `lo` to `probe + 1`. If bigger, move `hi` to `probe - 1`.
6. Repeat until you find the key or the range is empty.

Watch the first probe in the demo. It often lands right on the key, or very close, on the first try.

## Time and space complexity

Best case, O(1): the first guess is right.

Average case, O(log log n), for values spread evenly (uniformly) over their range. That grows unbelievably slowly: for a billion values, `log₂ log₂ n` is about 5. Each good guess shrinks the range far more than a halving does.

Worst case, O(n): skewed values. Picture `[1, 2, 3, 4, 5, 6, 7, 8, 9, 1000]` and a search for 9. The huge last value makes every guess land near the start, and the search creeps forward one step at a time, like a linear search.

Space is O(1). Two bounds and a probe.

## Common mistakes

- Dividing by zero. If `a[hi] == a[lo]`, the formula breaks. Check for it and probe `lo` directly.
- Skipping the range check. If the key is below `a[lo]` or above `a[hi]`, the formula gives a position outside the list.
- Doing the math with floats and rounding the wrong way. Use integer math, multiplying before dividing, so the probe stays inside `[lo, hi]`.
- Using it on data you know nothing about. On skewed data it can be far slower than binary search.

## When to use it

Use it when the data is sorted, large, and spread fairly evenly: sequential IDs, timestamps at a steady rate, or evenly distributed numbers. That is also the idea behind some database indexes that learn how the data is spread and jump straight to it.

When you don’t know how the data is spread, binary search is the safer choice. It guarantees O(log n) no matter what. A common compromise is to start with interpolation and switch to binary search if the guesses aren’t shrinking the range fast enough.

## Code

### Python

```python
def interpolation_search(a, key):
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= key <= a[hi]:
        x, d, r = a[lo], a[hi]-a[lo], hi-lo
        probe=lo if d==0 else lo+(key-x)*r//d
        if a[probe] == key: return probe
        if a[probe] < key: lo = probe+1
        else: hi = probe-1
    if lo <= hi: lo = hi + 1
    return -1
```

### TypeScript

```ts
function interpolationSearch(a: number[], key: number) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi && a[lo] <= key && key <= a[hi]) {
    const x = a[lo], d = a[hi] - a[lo], r = hi - lo;
    let probe = lo;
    if (d !== 0) probe += Math.floor(((key - x) * r) / d);
    if (a[probe] === key) return probe;
    if (a[probe] < key) lo = probe + 1;
    else hi = probe - 1;
  }
  if (lo <= hi) lo = hi + 1;
  return -1;
}
```

### Go

```go
func interpolationSearch(a []int, key int) int {
    lo, hi := 0, len(a)-1
    for lo <= hi && a[lo] <= key && key <= a[hi] {
        x, d, r := a[lo], a[hi]-a[lo], hi-lo
        probe := lo
        if d != 0 {
            probe = lo + (key-x)*r/d
        }
        if a[probe] == key {
            return probe
        }
        if a[probe] < key {
            lo = probe + 1
        } else {
            hi = probe - 1
        }
    }
    if lo <= hi {
        lo = hi + 1
    }
    return -1
}
```

## Questions

### Is interpolation search faster than binary search?

On evenly spread data, yes: O(log log n) against O(log n). On skewed data it can drop to O(n), which is much worse.

### Does interpolation search need sorted data?

Yes. The guess only makes sense if the values increase along the list.

### What does interpolate mean here?

Estimating a position between two known points. Here, the two known points are the values at `lo` and `hi`.

## 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.
- [Exponential Search](https://www.tmread.me/algorithms/exponential-search.md): Double a bound until it passes the key, then binary search that range.
- [Jump Search](https://www.tmread.me/algorithms/jump-search.md): Jump ahead √n at a time, then walk back through one block.

---

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