Interpolation Search

Like binary search, but instead of always probing the middle it estimates where the target should sit from the values at the window ends — assuming roughly uniform spacing. On uniformly distributed data this reaches O(log log n); on skewed data it degrades to O(n).

Best

O(1)

Average

O(log log n)

Worst

O(n)

Space

O(1)