A smarter probe position
Binary search always looks at the middle. Interpolation search instead guesses where the target should be, the way you flip near the back of a phone book for a name starting with W rather than opening to the center.
The estimate
- Assume the values are spread roughly uniformly across the range.
- Use the target's value, relative to the lowest and highest in the live range, to compute a proportional probe index.
- If the target sits about seventy percent of the way up in value, probe about seventy percent of the way along the indices.
Behaviour
- On data that really is evenly distributed, the probe lands very close to the target, so the search can finish in remarkably few steps.
- On skewed or clustered data the estimate can be wildly off, and performance degrades, in the worst case scanning almost everything.
Practical guidance
- Reserve it for large, numeric, smoothly distributed keys.
- Guard against division by zero when the range has equal endpoints.
- When in doubt, plain binary search is the safer default because its bound does not depend on distribution.
Key idea
Interpolation search predicts the target position from its value, excelling on uniform numeric data but faltering when the distribution is skewed.