Interpolation Search

W. W. Peterson, 1970

Introduced by W. W. Peterson in 1970, interpolation search improves on binary search for uniformly distributed data by estimating where the target lies based on its value relative to the endpoints of the current range. Instead of always probing the midpoint, it calculates a position proportional to the target's value, achieving O(log log n) average time on uniform data. The visualization shows sorted cells with the active range in teal, the computed probe position in gold, eliminated portions faded, and the formula displayed below.