Interpolation search

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 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})).

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

www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?