Než se naučíme binární vyhledávání, naučme se:
Co je vyhledávání?
Hledat je nástroj, který uživateli umožňuje vyhledávat dokumenty, soubory, média nebo jakýkoli jiný typ dat uchovávaných v databázi. Hledání funguje na jednoduchém principu shody kritérií se záznamy a jejich zobrazení uživateli. Tímto způsobem funguje nejzákladnější vyhledávací funkce.
Co je to binární vyhledávání?
Binární vyhledávání je pokročilý typ vyhledávacího algoritmu, který vyhledává a načítá data z seřazeného seznamu položek. Jeho hlavní pracovní princip spočívá v rozdělení dat v seznamu na polovinu, dokud není požadovaná hodnota nalezena a zobrazena uživateli ve výsledku vyhledávání. Binární vyhledávání je běžně známé jako hledání v polovině intervalu nebo logaritmické vyhledávání .
V tomto kurzu algoritmu se naučíte:
- Co je vyhledávání?
- Co je to binární vyhledávání?
- Jak funguje binární vyhledávání?
- Příklad binárního vyhledávání
- Proč potřebujeme binární vyhledávání?
Jak funguje binární vyhledávání?
Binární vyhledávání funguje následujícím způsobem:
- Proces vyhledávání se zahájí vyhledáním prostředního prvku seřazeného pole dat
- Poté se hodnota klíče porovná s prvkem
- Pokud je klíčová hodnota menší než prostřední prvek, pak vyhledávání analyzuje horní hodnoty středního prvku pro srovnání a shodu
- V případě, že klíčová hodnota je větší než prostřední prvek, pak vyhledávání analyzuje nižší hodnoty středního prvku pro srovnání a shodu
Příklad binárního vyhledávání
Podívejme se na příklad slovníku. Pokud potřebujete najít určité slovo, nikdo neprochází každým slovem postupně, ale náhodně vyhledá nejbližší slova, aby hledal požadované slovo.
Obrázek nahoře ilustruje následující:
- Máte pole 10 číslic a prvek 59 je třeba najít.
- Všechny prvky jsou označeny indexem od 0 do 9. Nyní se vypočítá střed pole. Chcete-li tak učinit, vezmete hodnoty indexu vlevo a vpravo a vydělíte je 2. Výsledkem je 4,5, ale vezmeme hodnotu podlahy. Proto je střed 4.
- Algoritmus vypustí všechny prvky ze střední (4) na nejnižší hranici, protože 59 je větší než 24 a nyní je pole ponecháno pouze s 5 prvky.
- Nyní je 59 větší než 45 a menší než 63. Střední je 7. Proto se pravá hodnota indexu změní na střední - 1, což se rovná 6, a hodnota levého indexu zůstane stejná jako dříve, což je 5.
- V tuto chvíli víte, že 59 přichází po 45. Levý index, který je 5, se tedy také stane středem.
- Tyto iterace pokračují, dokud se pole nezredukuje pouze na jeden prvek, nebo dokud se nalezená položka nestane středem pole.
Příklad 2
Podívejme se na následující příklad, abychom porozuměli fungování binárního vyhledávání
- Máte řadu seřazených hodnot v rozmezí od 2 do 20 a musíte najít 18.
- Průměr dolní a horní meze je (l + r) / 2 = 4. Hledaná hodnota je větší než střední hodnota, která je 4.
- Hodnoty pole menší než střední jsou vynechány z vyhledávání a hodnoty větší než střední hodnota 4 jsou prohledány.
- Toto je opakující se proces dělení, dokud není nalezena skutečná položka, která má být prohledána.
Proč potřebujeme binární vyhledávání?
Následující důvody činí z binárního vyhledávání lepší volbu pro použití jako vyhledávací algoritmus:
- Binární vyhledávání funguje efektivně na tříděných datech bez ohledu na velikost dat
- Namísto provádění vyhledávání procházením dat v sekvenci binární algoritmus náhodně přistupuje k datům, aby našel požadovaný prvek. Díky tomu jsou vyhledávací cykly kratší a přesnější.
- Binární vyhledávání provádí srovnání seřazených dat na základě principu řazení, než při použití porovnání rovnosti, která jsou pomalejší a většinou nepřesná.
- Po každém cyklu vyhledávání algoritmus rozdělí velikost pole na polovinu, takže v další iteraci bude fungovat pouze ve zbývající polovině pole
souhrn
- Hledat je nástroj, který uživateli umožňuje vyhledávat dokumenty, soubory a další typy dat. Binární vyhledávání je pokročilý typ vyhledávacího algoritmu, který vyhledává a načítá data z seřazeného seznamu položek.
- Binární vyhledávání je běžně známé jako hledání v polovině intervalu nebo logaritmické vyhledávání
- Funguje to tak, že při každé iteraci pod nalezeným požadovaným prvkem se pole rozdělí na polovinu.
- Binární algoritmus zabírá střed pole vydělením součtu hodnot indexu vlevo a vpravo číslem 2. Nyní algoritmus zruší dolní nebo horní hranici prvků ze středu pole v závislosti na prvku, který má být nalezen .
- Algoritmus náhodně přistupuje k datům, aby našel požadovaný prvek. Díky tomu jsou vyhledávací cykly kratší a přesnější.
- Binární vyhledávání provádí srovnání seřazených dat na základě principu řazení, než při použití pomalého a nepřesného srovnání rovnosti.
- Binární vyhledávání není vhodné pro netříděná data.