Binární vyhledávání
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 žř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);
}
Díky.