Obsah:
Definícia - Čo znamená binárne vyhľadávanie?
Algoritmus binárneho vyhľadávania sa používa na nájdenie polohy špecifickej hodnoty obsiahnutej v triedenom poli. Pri práci na princípe delenia a dobývania môže byť tento vyhľadávací algoritmus pomerne rýchly, ale je potrebné si uvedomiť, že údaje musia byť usporiadané. Funguje tak, že sa začne vyhľadávanie v strede poľa a pracuje sa nadol v prvej dolnej alebo hornej polovici sekvencie. Ak je stredná hodnota nižšia ako cieľová hodnota, znamená to, že vyhľadávanie musí ísť vyššie, ak nie, musí sa pozrieť na zostupnú časť poľa.
Binárne vyhľadávanie je tiež známe ako vyhľadávanie v polovici intervalu alebo logaritmické vyhľadávanie.
Techopedia vysvetľuje binárne vyhľadávanie
Binárne vyhľadávanie je rýchly a efektívny spôsob nájdenia konkrétnej cieľovej hodnoty zo sady objednaných položiek. Začatím uprostred zoradeného zoznamu môže efektívne skrátiť hľadaný priestor na polovicu určením, či má zoznam stúpať alebo zostupovať na základe strednej hodnoty v porovnaní s cieľovou hodnotou.
Napríklad s cieľovou hodnotou 8 a vyhľadávacím priestorom 1 až 11:
- Zistí sa stredná / stredná hodnota a nastaví sa ukazovateľ, ktorý je v tomto prípade 6.
- Cieľ 8 je porovnávaný so 6. Keďže 6 je menší ako 8, cieľ musí byť vo vyššej polovici.
- Ukazovateľ sa presunie na nasledujúcu hodnotu (7) a porovná sa s cieľom. Je menšia, preto sa ukazovateľ posunie na nasledujúcu vyššiu hodnotu.
- Ukazovateľ je teraz na 8. V porovnaní s cieľom je to presná zhoda, preto bol cieľ nájdený.
Pri použití binárneho vyhľadávania sa cieľ musel porovnávať iba s tromi hodnotami. Oproti lineárnemu vyhľadávaniu by to začalo od prvej hodnoty a posunulo sa hore, pričom by bolo potrebné porovnať cieľ s ôsmimi hodnotami. Binárne vyhľadávanie je možné iba pri objednanom súbore údajov; ak sú údaje náhodne usporiadané, potom by lineárne vyhľadávanie vždy prinieslo výsledky, zatiaľ čo binárne vyhľadávanie by pravdepodobne zostalo zaseknuté v nekonečnej slučke.
