information:classification, linguistic:translation
Interpolation search

Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. It works on the basis that the midpoint is not the best guess in many cases. For example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array.

A common interpolation function is linear interpolation. If A {\displaystyle A} is the array, L, R {\displaystyle L,R} are the lower and upper bounds respectively, and T {\displaystyle T} is the target, then the target is estimated to be about (T − A L) / (A R − A L) {\displaystyle (T-A_{L})/(A_{R}-A_{L})} of the way between L {\displaystyle L} and R {\displaystyle R}. When linear interpolation is used, and the distribution of the array elements is uniform or near uniform, interpolation search makes O (log log n) {\textstyle O(\log \log n)} comparisons.

In practice, interpolation search is slower than binary search for small arrays, as interpolation search requires extra computation. Its time complexity grows more slowly than binary search, but this only compensates for the extra computation for large arrays.