- Target
- Still possible
- Compared
- Ruled out
- Found
Interpolation search
Interpolation search looks for a value in a sorted list the way you open a phone book: for a name starting with T you open near the back, not in the middle. It estimates the target's place from the values at both ends of the part that is left. Choose the value and how the values are spread, step through the probes, and see when the estimate beats binary search and when it does not. Press Play to watch the search, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. The dashed line marks the value you search for, and the shaded part is where it can still be. Interpolation search needs a sorted list, so an unsorted list is sorted first. Choose the value, how the values are spread, how many bars, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose the value to search for, how the values are spread, and how many bars. Or type your own numbers: interpolation search sorts them first.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere in the search.
- Switch Spread between Even, Random gaps and Skewed, and compare Probes with Binary search would need.
How interpolation search works
Look at the first and last value of the part of the sorted list that can still hold the target. If the target lies, say, 40% of the way from the first value to the last, probe the place 40% of the way along. If the value there is the target, you are done. If it is smaller, only the places after it are left; if larger, only the places before it. Estimate again in what is left. If the target is smaller than the first value or larger than the last, it is not there.
When the estimate works
If the values are spread evenly, like 10, 20, 30 and so on, the first estimate lands on the target or very close to it, and the search needs about log₂(log₂ n) probes on average: around 5 for a billion values, against 30 for binary search. If the values bunch up, like 1, 2, 3, 4, 1000, the estimates keep landing in the wrong place and each probe may only remove one value, so the worst case is n probes. Binary search never does worse than about log₂ n.
Frequently asked questions
How does interpolation search work?
On a sorted list it estimates where the target should be from the first and last value of the part that is left, probes that place, and keeps only the part on the correct side. It is like binary search with a smarter guess than the middle.
Is interpolation search faster than binary search?
On evenly spread values, yes: about log₂(log₂ n) probes on average instead of about log₂ n. On unevenly spread values it can be much slower, up to n probes, while binary search never needs more than about log₂ n.
Why can it be slow?
Because the estimate assumes the values grow evenly. If most values are small and a few are huge, the estimate for a small target lands near the start again and again and only removes one or two values each time.
Where is interpolation search used?
Where keys are close to evenly spread and probes are expensive, such as looking up records by numeric ID or hash on disk. Many systems combine it with binary search to keep a good worst case.
Are my numbers sent anywhere?
No. The search runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor