Interpolační vyhledávání

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 $O(\\log(\\log{n}))$ .

Kód

Java

     /**
      * Interpolacni vyhledavani (pole razene od nejnizsiho k nejvyssimu)
      * @param array prohledavane pole
      * @param value hledana hodnota
      * @param from prvni prvek, na ktery se smi sahnout
      * @param to posledni prvek, na ktery se smi sahnout
      * @return index hledaneho prvku, -1 v pripade nenalezeni
      */
     public static int interpolationSearch(int[] array, int value, int from, int to){
         if(array[from] == value) return from; //nalezli jsme, treba kontrolovat kvuli deleni nulou dale v algoritmu
         else if(from == to || array[from] ==  array[to]) return -1; //zarazka rekurze
 
         //provedeme odhad pozice hledaneho cisla na zaklade soucasneho rozsahu pozic, hodnot mezi a hledane hodnoty
         int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);
         
         if(array[index] == value) return index;//cislo jsme nalezli
         //nenalezli jsme, pokracujeme v prave polovine, pokud je hledane cislo vyssi nez predel
         else if(array[index] < value) return interpolationSearch(array, value, index + 1, to);
         //nenalezli jsme, pokracujeme v leve polovine, pokud je hledane cislo nizsi nez predel
         else return interpolationSearch(array, value, from, index - 1);
     }

Princip

Kód

Doporučujeme