Interpolation search, explained

When you look for "Zhang" in a phone book you do not open it in the middle. You open it near the end, because you expect that name to be there. Interpolation search does the same thing with numbers.

It uses the target value and the values at the ends of the current range to estimate a position, then checks that position.

How it works

• Estimate a position from the target value and the values at both ends of the range.
• Check the item at that position.
• If it matches, stop. If it is too small, search to the right. If it is too big, search to the left.
• Make a new estimate for the smaller range and repeat.

A small example

Search for 23 in this sorted list:

2 5 8 12 16 23 38 56 72 91

The value 23 is closer to the start than the end of the value range, so the first estimate lands near the left side instead of the middle. The checks go 8, 12, 16 and then 23. Total:

4 checks

On this short list that is one more than binary search needed (3). Interpolation search pays off on long lists whose values are spread evenly.

What to know about its cost

• About O(log log n) when the values are evenly spread.
• Worst case O(n) when the values are very uneven.
• Needs a sorted list and uses O(1) extra space.

Where it works well

• Very fast on evenly spread numbers.
• Can beat binary search on large, smooth data.

Where it struggles

• Slow when values are clustered or grow very quickly.
• Needs numbers, so that it can estimate a position.

Try it yourself

Open the Searching experiment, enter the list from this post, set the target to 23, choose Interpolation Search and step through it. Then compare it with the other algorithms and look at how many positions each one checks.

Open the Searching experiment