Interpolation search
When you look up "Taylor" in a phone book, you do not open it in the middle: you open it near the back, because T is late in the alphabet. Interpolation search does the same with numbers. It guesses where the target should be from how large it is, and on evenly spread data that guess is remarkably good.
The idea
Binary search always probes the middle, whatever it is looking for. Interpolation search uses the values. If the part of the list that is left runs from 10 to 100 and the target is 70, the target lies two thirds of the way from the first value to the last, so it probes two thirds of the way along. In formula form, the probe is at lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). After the probe it keeps the part on the correct side, exactly like binary search, and estimates again.
Two examples
In 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, searching for 70 probes place 7 straight away: found in 1 probe, where binary search needs 4. Now take 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 and search for 9. Because of the 999, every estimate lands near the start: the search probes 1, 2, 3 and so on, one place at a time, and needs 9 probes where binary search needs 3.
How fast it is
When the values are spread evenly, or drawn at random from an even distribution, each probe shrinks the part that is left from about n to about √n. That gives about log₂(log₂ n) probes on average: around 5 even for a billion values, against 30 for binary search. When the values are spread very unevenly, a probe can remove as little as one value, and the worst case is n probes, as bad as linear search. Each probe also costs a division, so in practice it pays off mainly when probes are expensive, such as reads from disk.
History and variants
W. W. Peterson described interpolation search in 1957, for finding records on random-access storage. Its log log n average for evenly spread keys was proved in 1978 by Perl, Itai and Avni. Practical versions guard against bad data by mixing in binary steps, for example interpolation-sequential search or interpolation-binary search, so that the worst case stays close to log n.
Explore it
Open the app, choose a value in Search for, and press Step. Each probe says how far the target lies between the two end values and which place that points to. Switch Spread to Even and most searches end in one probe; switch it to Skewed and the probes creep along the start of the list. The last tile shows how many steps binary search would need for the same value.
Frequently asked questions
What is the time complexity of interpolation search?
O(log log n) on average for evenly spread values, and O(n) in the worst case. It needs O(1) extra memory and a sorted list.
What is the difference between interpolation search and binary search?
Binary search always probes the middle of what is left. Interpolation search probes where the target should be, judging by the values at both ends. That is much better on evenly spread values and can be much worse on skewed ones.
What kind of data suits interpolation search?
Sorted numeric keys that are spread fairly evenly: sequential IDs with few gaps, timestamps of regular events, or hashed keys. It suits data where a probe is expensive and a little arithmetic is cheap.
Why does the app offer different spreads?
Because the spread decides how good the estimates are. Even values make interpolation search look almost magical, and skewed values show its weakness. Comparing them with the binary search count is the clearest way to see when to use which.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try interpolation search