Toggle navigation

Interpolation searchTaste of algorithms in JAVA

The interpolation search is an improvement of the binary search for instances, where the values in the array are ordered and uniformly distributed.


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 p, where the value should be placed in accordance to the distribution of values a splits the array at p. If the array contains numbers 0, 1,\\; 2, \\cdots,\\; 10 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 O(\\log(\\log{n})).


     * 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);

INFO WEB s.r.o.

Company INFO WEB s.r.o. offers development of systems, GIS, presentations and interactive maps, using the microcontrollers from the IoT (Tnternet of Things) technology. Beside this on PROGRAMMING-ALGORITHMS.NET we publish some of the algorithms, which helps to solve some of the spatial analysis and spatial problems, conversion of coordinate systems and helps to solve standard computing operations.


Place for your banner

Here is the position ready for our customer's banners.