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
01./**02. * Interpolation search03. * @param array array with uniformly distributed values in ascending order04. * @param value searched value05. * @param from first index that might be touched06. * @param to last index that might be touched07. * @return index index of the searched value in the array, -1 if not found08. */09.public static int interpolationSearch(int[] array, int value, int from, int to){10. if(array[from] == value) return from; 11. else if(from == to || array[from] == array[to]) return -1; //not found12. 13. //probable position of the searched value14. int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);15. 16. if(array[index] == value) return index;//found17. //continue in the right part of the array18. else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);19. //continue in the left part of the array20. else return interpolationSearch(array, value, from, index - 1);21.}