Interpolation Search - Sample Implementation

Sample Implementation

The following code example for the Java programming language is a simple implementation. At each stage it computes a probe position then as with the binary search, moves either the upper or lower bound in to define a smaller interval containing the sought value. Unlike the binary search which guarantees a halving of the interval's size with each stage, a misled interpolation may reduce/increase the mid index by only one, thus resulting in a worst-case efficiency of O(n).

public int interpolationSearch(int sortedArray, int toFind){ // Returns index of toFind in sortedArray, or -1 if not found int low = 0; int high = sortedArray.length - 1; int mid; while (sortedArray <= toFind && sortedArray >= toFind) { mid = low + ((toFind - sortedArray) * (high - low)) / (sortedArray - sortedArray); //out of range is possible here if (sortedArray < toFind) low = mid + 1; else if (sortedArray > toFind) // Repetition of the comparison code is forced by syntax limitations. high = mid - 1; else return mid; } if (sortedArray == toFind) return low; else return -1; // Not found }

Notice that having probed the list at index mid, for reasons of loop control administration, this code sets either high or low to be not mid but an adjacent index, which location is then probed during the next iteration. Since an adjacent entry's value will not be much different the interpolation calculation is not much improved by this one step adjustment, at the cost of an additional reference to distant memory such as disc.

Each iteration of the above code requires between five and six comparisons (the extra is due to the repetitions needed to distinguish the three states of < > and = via binary comparisons in the absence of a three-way comparison) plus some messy arithmetic, while the binary search algorithm can be written with one comparison per iteration and uses only trivial integer arithmetic. It would thereby search an array of a million elements with no more than twenty comparisons (involving accesses to slow memory where the array elements are stored); to beat that the interpolation search as written above would be allowed no more than three iterations.