Interpolation Search Algorithm

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).By comparison, binary search always chooses the center of the remaining search space, discarding one half or the other, depending on the comparison between the key found at the estimated position and the key seek — it makes not necessitate numerical values for the keys, exactly a total order on them.

Interpolation Search source code, pseudocode and analysis

It can be useful for locating a record in a large sorted file on disk, where each probe necessitates a disk seek and is much slower than the interpolation arithmetical. index structures like B-trees also reduce the number of disk accesses, and are more often used to index on-disk data in part because they can index many types of data and can be updated online.