Interpolation Search

Interpolation search is what you actually do with a phone book. Looking for “Wilson,” you do not open to the dead center; you flip near the back, because the names run in order and you know roughly where W lands. Interpolation search does the same arithmetic. It assumes the values climb at a steady rate across the window and computes where the target should be, then probes there instead of at the middle.

When that assumption holds — values spread out evenly, which is exactly what this visualizer generates — the guess is almost right every time, and the window collapses in about O(log log n) probes. That is dramatically fewer than binary search’s O(log n): where binary needs twenty probes for a million items, interpolation often needs four or five. The catch is that it is a bet on the distribution. Feed it clustered or skewed data and the guesses miss badly, dragging it toward O(n). Binary search’s halving makes no such assumption, which is why it is the safer default.

Watch the gold playhead land wherever the value estimate points rather than the middle — on evenly spaced numbers it leaps almost straight to the answer. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.