AlgoLab

Interpolation search

Interpolation search estimates where the target is likely to be, proportional to where its value falls between the values at the low and high boundaries, and checks that position directly instead of always checking the midpoint. On values that are roughly uniformly spread out, this estimate lands close to the target almost immediately.

When it is the right choice

Interpolation search is worth using in place of binary search when the data is numeric and roughly uniformly distributed, where its average case of O(log log n) comparisons is a real improvement over binary search's O(log n). It is a poor choice when the data is clustered — bunched tightly in places with a few outliers far away — where its estimate keeps landing short of a distant target and it degrades toward a slow, near-linear scan.

How it works

• Set the low and high boundaries to the first and last position of the array.
• If the target is outside the values at the low and high boundaries, it cannot be in the array.
• Otherwise, estimate the target's position, proportional to where its value falls between the low and high values.
• Compare the value at the estimated position with the target.
• If it matches, the target is found.
• If the value there is smaller than the target, search the range above the estimated position.
• If the value there is larger than the target, search the range below the estimated position.
• If the range becomes empty, or the target falls outside it, the target is not in the array.

Worth noticing

• Its performance depends entirely on how the data is distributed: uniformly spread values give it O(log log n) average comparisons, but tightly clustered values with a few distant outliers push it toward its O(n) worst case — this tool's clustered preset exists to show exactly that degradation.
• It only works on sorted numeric data — like binary search, running it on unsorted data can give a wrong answer without any error.
• When every remaining value is equal (the low and high boundary values match), the proportional estimate would divide by zero; this implementation falls back to checking the low boundary directly in that case.

Cost

Best

O(1)

Average

O(log log n)

Worst

O(n)

Extra space

O(1)

Worth comparing

• Binary search — Binary search always checks the midpoint; interpolation search checks wherever the value should be — a better bet on uniform data, a worse one on clustered data.
• Jump search — All three searches narrow a sorted range a different way: halving, jumping in blocks, or estimating a position.

All algorithms