Interpolační vyhledávání je vylepšením binárního vyhledávání pro případ, kdy víme, že jsou čísla v poli nejen seřazená, ale také rovnoměrně rozložená.
Princip
Interpolační vyhledávání vychází z úvahy, že pokud máme v poli například čísla od 0 do 100 a hledáme číslo 2, tak je přinejmenším nerozumné pole binárně dělit (napřed se podívat na index 50, pak 25, pak 12...), ale je daleko rozumnějsí se podívat někam kolem indexu 2, kde by se číslo mělo nacházet (vzhledem k rovnoměrnému rozložení). Složitost tohoto přístupu je .
Kód
01./**02. * Interpolacni vyhledavani (pole razene od nejnizsiho k nejvyssimu)03. * @param array prohledavane pole04. * @param value hledana hodnota05. * @param from prvni prvek, na ktery se smi sahnout06. * @param to posledni prvek, na ktery se smi sahnout07. * @return index hledaneho prvku, -1 v pripade nenalezeni08. */09.public static int interpolationSearch(int[] array, int value, int from, int to){10. if(array[from] == value) return from; //nalezli jsme, treba kontrolovat kvuli deleni nulou dale v algoritmu11. else if(from == to || array[from] == array[to]) return -1; //zarazka rekurze12. 13. //provedeme odhad pozice hledaneho cisla na zaklade soucasneho rozsahu pozic, hodnot mezi a hledane hodnoty14. int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);15. 16. if(array[index] == value) return index;//cislo jsme nalezli17. //nenalezli jsme, pokracujeme v prave polovine, pokud je hledane cislo vyssi nez predel18. else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);19. //nenalezli jsme, pokracujeme v leve polovine, pokud je hledane cislo nizsi nez predel20. else return interpolationSearch(array, value, from, index - 1);21.}