Obsah:
Definice - Co znamená Binární vyhledávání?
Algoritmus binárního vyhledávání se používá k nalezení polohy konkrétní hodnoty obsažené v seřazeném poli. Při práci na principu dělení a dobývání může být tento vyhledávací algoritmus poměrně rychlý, ale je třeba si uvědomit, že data musí být ve tříděné podobě. Funguje tak, že začíná vyhledávání ve středu pole a pracuje dolů první dolní nebo horní polovině sekvence. Pokud je střední hodnota nižší než cílová hodnota, znamená to, že vyhledávání musí jít výš, pokud ne, musí se podívat na sestupnou část pole.
Binární vyhledávání je také známé jako vyhledávání v polovičním intervalu nebo logaritmické vyhledávání.
Techopedia vysvětluje binární vyhledávání
Binární vyhledávání je rychlá a efektivní metoda nalezení konkrétní cílové hodnoty ze sady objednaných položek. Začátkem uprostřed roztříděného seznamu může efektivně zkrátit vyhledávací prostor na polovinu určením, zda se má seznam vzestupně nebo sestupně opírat o střední hodnotu ve srovnání s cílovou hodnotou.
Například s cílovou hodnotou 8 a vyhledávacím prostorem 1 až 11:
- Nalezne se střední / střední hodnota a tam se nastaví ukazatel, což je v tomto případě 6.
- Cíl 8 je ve srovnání se 6. Protože 6 je menší než 8, musí být cíl ve vyšší polovině.
- Ukazatel se přesune na další hodnotu (7) a porovná se s cílem. Je menší, proto se ukazatel přesune na další vyšší hodnotu.
- Ukazatel je nyní na 8. Ve srovnání s cílem je to přesná shoda, proto byl cíl nalezen.
Pomocí binárního vyhledávání musel být cíl porovnáván pouze se třemi hodnotami. Ve srovnání s lineárním vyhledáváním by to začalo od první hodnoty a posunulo se nahoru, bylo by potřeba porovnat cíl s osmi hodnotami. Binární vyhledávání je možné pouze s uspořádanou sadou dat; pokud jsou data náhodně uspořádána, pak by lineární vyhledávání vedlo vždy k výsledkům, zatímco binární vyhledávání by pravděpodobně bylo zaseknuto v nekonečné smyčce.
