Interpolation Search

Predicts the target's index by linear interpolation on value — near O(log log n) on uniformly distributed data.