Interpolation search

From Wikipedia, the free encyclopedia

Interpolation search parallels how humans search through a telephone book. Instead of comparing against every item like the linear search, it attempts to find the item by approximating how far the item is likely to be from the current position. This differs from the binary search, in that the binary search always divides the search space in half. On average the interpolation search makes about log(log(N)) comparisons (if the elements are uniformly distributed), where N is the number of elements to be searched. In a worst case scenario, where the items increase exponentially it can make up to O(n) comparisons.

In reality, interpolation search is often no faster than binary search due to the complexity of the arithmetic calculations of approximating the indices.

Interpolation search, like binary search, requires that the values be sorted and randomly accessible. It works by making the assumption that values are uniformly distributed, and thus uses the end values to compute an index.

The following code example for the Java programming language is a simple implementation.

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[low] < toFind && sortedArray[high] >= toFind) {
  mid = low + ((toFind - sortedArray[low]) * (high - low))/ (sortedArray[high] - sortedArray[low]);

  if (sortedArray[mid] < toFind)
   low = mid + 1;
  else if (sortedArray[mid] > toFind)
   high = mid - 1;
  else
   return mid;
 }

 if (sortedArray[low] == toFind)
  return low;
 else
  return -1; // Not found
}