The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.
Description
The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element. Interpolation search calculates a position , where the value should be placed in accordance to the distribution of values a splits the array at
. If the array contains numbers
and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found). The interpolation search calculates the probable position (index 9) and immediately finds the value. The expected complexity of the interpolation search in
.
Code
/**
* Interpolation search
* @param array array with uniformly distributed values in ascending order
* @param value searched value
* @param from first index that might be touched
* @param to last index that might be touched
* @return index index of the searched value in the array, -1 if not found
*/
public static int interpolationSearch(int[] array, int value, int from, int to){
if(array[from] == value) return from;
else if(from == to || array[from] == array[to]) return -1; //not found
//probable position of the searched value
int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);
if(array[index] == value) return index;//found
//continue in the right part of the array
else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);
//continue in the left part of the array
else return interpolationSearch(array, value, from, index - 1);
}