Home/Searching/Interpolation search
Search algorithmsCTRL K

Interpolation search

· guess the position from the value
/searching/interpolation-search
COMPARISONS
0
probes so far
RANGE
32/ 32
elements still possible
ESTIMATE
—
position by proportion
TARGET
33
value we look for
RESULT
—
index once found
discardedprobetargetfound
n = 32 · target 33 · seed 7 · uniform values · 6 steps
step 0 / 5
Size32
interpolation_search.ts
1
function interpolationSearch(array: number[], target: number) {
2
  let low = 0, high = array.length - 1;
3
  while (low <= high && target >= array[low] && target <= array[high]) {
4
    const position = low + Math.floor(((target - array[low]) * (high - low)) / (array[high] - array[low]));
5
    if (array[position] === target) return position;
6
    if (array[position] < target) low = position + 1;
7
    else high = position - 1;
8
  }
9
  return -1;
10
}
CURRENT STEP
line 2

Look for 33 in [0, 31]. The values run from 7 to 97, so the position can be estimated by proportion.

// how it works

Understanding Interpolation search

interpolation search · how you open a phone book at the S, not in the middle
01

The idea

Binary search always probes the middle. Interpolation search probes where the target would be if the values were spread evenly: a target near the low end of the value range gets a probe near the low end of the index range. The estimate is a straight-line interpolation between the two ends.

When the values really are uniform the range shrinks from n to about √n per probe, which gives log log n probes: four for a million elements. When they are not, a skewed distribution can push every probe one step at a time and the search degrades to linear.

02

The four stages

1
estimatelow + (target − array[low]) × (high − low) / (array[high] − array[low])
2
probethe estimated position
3
narrowkeep the side that can hold the target
4
foundor the target falls outside the range
03

Complexity

best
O(1)the estimate is exact
average
O(log log n)uniformly distributed values
worst
O(n)exponentially spread values
space
O(1)two indices
04

Versus its siblings

COMPARISONS AT N = 1 000 · TARGET PRESENT
linear
500
jump
63
binary
10
ternary
13
interpolation
4
average over random targets · sorted, uniform values
05

Pseudocode

INTERPOLATIONSEARCH(array, target)
  low ← 0; high ← n − 1
  while low ≤ high and array[low] ≤ target ≤ array[high]
    position ← low + ⌊(target − array[low]) × (high − low) / (array[high] − array[low])⌋
    if array[position] = target: return position
    if array[position] < target: low ← position + 1 else high ← position − 1
  return −1
06

When to use

Large sorted arrays of roughly uniform numeric keys: timestamps, sequential ids, sensor readings.
When each probe is expensive (a disk seek, a network round trip) and the distribution is known to be smooth.
07

Pitfalls

A few outliers at the ends wreck the estimate; clamp it or fall back to binary search after a bad probe.
Integer overflow in (target − low) × (high − low) on large keys; use 64-bit or floating point.
Division by zero when array[high] equals array[low]; check it first.
08

History

W. W. Peterson proposed it in 1957 for searching sorted files on disk. Yehoshua Perl, Alon Itai and Haim Avni proved the log log n average in 1978, and Gonnet showed how badly it can do on non-uniform data, which is why binary search stayed the default.

Back to Searching