The interpolation search is to the binary search as the false-position method is to the binary search: Assuming that the list is approximately uniform (a plot of i versus array[i] is approximately linear), then when searching for a value obj, rather than selecting the middle entry with b = a + (c - a)/2, select the value b = a + round( (c - a)*(object - array[a])/(array[b] - array[a])). For values of obj close to array[a], the value b will be close to a; while if obj is close to array[c], then the value b will be closer to c.

Assuming the distribution is uniform, the run time is O(ln(ln(n))); however, like the false-position method, there are pathological examples where the search will require O(n) time. For example, any array which stores exponentially increasing values will, for numbers found in the first half of the array, require O(n) time. An easy-to-visualize pathological case is an array of n entries:

The enhanced array- and pointer-based implementations use binary search for arrays of size 500 or less.