Interpolation search

Prerequisites

• Binary search: interpolation search changes only how the probe is chosen.
• Proportions: "60 is 5/6 of the way from 10 to 70".
• Integer division in C.

The analogy

How it works

Data requirement: the array must be sorted, and the values should be roughly uniformly distributed for the speed-up.

Start with one search by hand

Look for 60 in [10, 20, 30, 40, 50, 60, 70] (indices 0 to 6). Guess first, then open "Check".

Finish the picture: a bad case

Now look for 6 in [1, 2, 3, 4, 5, 6, 1000]. The values are not evenly spread.

• First probe. 6 is $5/999$ of the way from 1 to 1000. Predict the index.
  Check

  $0 + 5 \cdot 6 / 999 \approx 0.03$, so index 0. a[0] = 1 is too small, so lo becomes 1.

• Next probes. The 1000 keeps dragging the estimate to the left edge. Predict how many probes in total.
  Check

  It probes index 0, 1, 2, 3, 4, then 5: 6 probes, one step at a time, like linear search.

The rule in plain words

Estimate where the target should be: as far along the range as the target is between the first and last values. Probe there.

If it's the target, done. Otherwise shrink the range to the correct side, exactly like binary search, and estimate again.

The code

Read this code after you have done one search by hand. It will make more sense.

int interpolation_search(const int a[], int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi && x >= a[lo] && x <= a[hi]) {   /* x must be in range */
        if (a[hi] == a[lo])                               /* avoid dividing by 0 */
            return a[lo] == x ? lo : -1;
        int pos = lo + (int)((long)(x - a[lo]) * (hi - lo) / (a[hi] - a[lo]));
        if (a[pos] == x) return pos;
        if (a[pos] < x) lo = pos + 1;
        else hi = pos - 1;
    }
    return -1;
}

flowchart TD
  A["lo = 0, hi = n - 1"] --> B{"lo <= hi and a[lo] <= x <= a[hi] ?"}
  B -->|no| F["Return -1"]
  B -->|yes| C["pos = estimate from the value of x"]
  C --> D{"compare a[pos] with x"}
  D -->|equal| E["Return pos"]
  D -->|"a[pos] < x"| G["lo = pos + 1"]
  D -->|"a[pos] > x"| H["hi = pos - 1"]
  G --> B
  H --> B
          

How fast is it?

The probe position is a straight-line estimate between the two ends of the range:

On uniformly spread values, the expected number of probes is $O(\log \log n)$. On skewed values, like the 1000 example, each probe may move only one step: $O(n)$.

Common mistakes

• Forgetting the a[hi] == a[lo] check, which divides by zero on runs of equal values.
• Computing (x - a[lo]) * (hi - lo) in int, which can overflow on large values.
• Quoting $O(\log \log n)$ without saying it only holds for uniformly distributed data.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• It probes near the target because it assumes values grow evenly from a[lo] to a[hi].
• It is $O(\log \log n)$ on uniform data because each good estimate shrinks the range far more than halving does.
• It is $O(n)$ in the worst case because skewed values can make every probe move just one step.
• It needs a zero-division guard because equal end values make the denominator zero.
• Extra space is $O(1)$ because it only keeps lo, hi and pos.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is interpolation search like using a phone book?
   Sample answer

   You open the book near where the name should be, near the end for "Williams", instead of in the middle. Interpolation search estimates the position from the value the same way.

2. Walk through a search for 60 in [10, 20, …, 70].
   Sample answer

   60 is 5/6 of the way from 10 to 70, so probe 5/6 of the way along indices 0..6: index 5, which holds 60. One probe.

3. Why does the code check a[hi] == a[lo] before computing pos?

   A good answer names the operation that fails.

   Sample answer

   The formula divides by a[hi] - a[lo]. If both ends are equal, that's division by zero, so we handle that case separately.

4. So what is interpolation search, in one sentence?
   Sample answer

   It's binary search on sorted data where the probe position is estimated from the target's value instead of always being the middle.

5. Why can it be as slow as linear search?

   A good answer uses the [1, 2, 3, 4, 5, 6, 1000] example.

   Sample answer

   When values are skewed, like one 1000 among small numbers, the estimate keeps landing at the left edge. Each probe then moves only one step, so it degrades to $O(n)$.

6. What are its best, average and worst cases?
   Sample answer

   Best $O(1)$, average $O(\log \log n)$ on uniformly distributed data, worst $O(n)$. Extra space $O(1)$.

7. When would you choose binary search instead?
   Sample answer

   When you don't know how the values are distributed, or they are clearly skewed. Binary search guarantees $O(\log n)$ no matter what.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the overflow cast and the $\log \log n$ derivation. I'd keep the phone-book analogy, the one-probe example, the skewed example, and "fast on even data, $O(n)$ on skewed data".

External resources

• GeeksforGeeks: Interpolation search: an article with code and the probe formula.
• Wikipedia: Interpolation search: history and complexity analysis.

Videos

• YouTube search: interpolation search explained: pick a short walkthrough.