# Interpolation search visualised: O(log log n) when uniform

> Interactive interpolation search: estimates the target position via linear interpolation. Extremely fast on uniformly distributed values, worst case still O(n).

Address: https://marckimmel.de/en/informatik/suchalgorithmen/interpolations-suche
Deutsche Fassung: https://marckimmel.de/informatik/suchalgorithmen/interpolations-suche.md

Estimates the position of the target via linear interpolation, almost like laying a ruler.

Interpolation Search is an extension of binary search that does not just take the middle, but estimates the index of the target via linear interpolation. From the current range a[lo] to a[hi] and the target value: pos = lo + ((target − a[lo]) · (hi − lo)) / (a[hi] − a[lo]). On uniformly distributed data this lands very close to the hit and the range shrinks faster than mere halving. Runtime on uniform data is O(log log n) on average, almost unbeatable. In the worst case (strongly non-uniform values like geometrically growing numbers) it degrades to O(n). Requires a sorted array with uniform values; on non-numeric or skewed data binary search is the better choice.

Optimal on large sorted data sets with uniformly distributed values, e.g. numeric indices or ID columns without gaps. Often risky on real data because the O(log log n) guarantee can flip to O(n); a classic technique in competitive programming.

## Related

- [Search Algorithms](https://marckimmel.de/en/informatik/suchalgorithmen.md)