Binární vyhledávání (hledané číslo: 6)

Binární vyhledávání (půlení intervalu) je vyhledávací technika, která zjišťuje pozici zadaného prvku v seřazeném poli. Na rozdíl od sekvenčního vyhledávání, které vyžaduje až operací, binární vyhledávání pracuje s asymptotickou složitostí .

Princip

Mějme sestupně seřazené pole a hledejme v něm prvek h. Binární vyhledávání v každém svém kroku zvolí prostřední prvek pole (p) a porovná jej s prvkem h. Pokud jsou tyto prvky totožné, tak vrátí index prvku p. Pokud má hledaný prvek vyšší hodnotu než p, tak je zřejmé, že h se musí nacházet v levé části pole. V opačném případě () se hledaný prvek musí nacházet v pravé části pole. Binární vyhledávání proto zavolá sebe sama na příslušnou perspektivní polovinu pole.

Protože dochází v každém kroku k půlení prohledávaného intervalu (a druhá polovina se nezpracovává), tak musí dojít k nalezení (nebo vyvrácení přítomnosti) hledaného prvku nejpozději v krocích.

Kód

    /**
     * Binarni vyhledavani
     * @param array prohledavane pole (setridene od nejvyssiho)
     * @param leftIndex prvni index, na ktery smime sahnout
     * @param rightIndex posledni index, na ktery smime sahnout
     * @param value hodnota k nalezeni
     * @return index hodnoty, -1 v pripade nenalezeni
     */
    public static int binarySearch(int[]  array, int leftIndex, int rightIndex, int value){
        if(leftIndex == rightIndex && array[leftIndex] != value) return -1;
    
        int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
        if(array[middleIndex] == value) return middleIndex;
        else if(array[middleIndex] > value) 
            return binarySearch(array, middleIndex + 1, rightIndex, value);
        else return binarySearch(array, leftIndex, Math.max(leftIndex, middleIndex - 1), value);
}