Binární vyhledávací algoritmus s PŘÍKLADEM

Než se naučíme binární vyhledávání, naučme se:

Co je vyhledávání?

Search je nástroj, který umožňuje svému uživateli najít dokumenty, soubory, média nebo jakýkoli jiný typ dat uložených v databázi. Vyhledávání funguje na jednoduchém principu přiřazování kritérií k záznamům a jejich zobrazení uživateli. Tímto způsobem funguje nejzákladnější vyhledávací funkce.

Co je binární vyhledávání?

Binární vyhledávání je pokročilý typ vyhledávacího algoritmu, který najde a načte data z setříděného seznamu položek. Jeho základní pracovní princip spočívá v dě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 a půlintervalové vyhledávání nebo logaritmické 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 hodnota klíče menší než prostřední prvek, pak vyhledávání analyzuje horní hodnoty k prostřednímu prvku pro porovnání a shodu
• V případě, že hodnota klíče je větší než prostřední prvek, pak prohledává a analyzuje nižší hodnoty až prostřední prvek pro porovná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é slovo sekvenčně, ale náhodně najde nejbližší slova a vyhledá požadované slovo.

Výše uvedený obrázek ilustruje následující:

1. Máte pole 10 číslic a je třeba najít prvek 59.
2. Všechny prvky jsou označeny indexem od 0 do 9. Nyní se vypočítá střed pole. Chcete-li to provést, vezmete hodnoty indexu nejvíce vlevo a vpravo a vydělíte je 2. Výsledek je 4.5, ale vezmeme minimální hodnotu. Střed je tedy 4.
3. Algoritmus vypustí všechny prvky ze středu (4) na nejnižší hranici, protože 59 je větší než 24 a pole nyní zbývá pouze s 5 prvky.
4. Nyní je 59 větší než 45 a menší než 63. Prostřední hodnota je 7. Pravá hodnota indexu se tedy stane středem – 1, což se rovná 6, a hodnota levého indexu zůstane stejná jako dříve, což je 5.
5. V tuto chvíli víte, že 59 následuje po 45. Proto se levý index, který je 5, také stane středem.
6. Tyto iterace pokračují, dokud není pole zredukováno 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 pochopili fungování binárního vyhledávání

1. Máte pole seřazených hodnot v rozsahu od 2 do 20 a potřebujete najít 18.
2. Průměr dolní a horní hranice je (l + r) / 2 = 4. Hledaná hodnota je větší než střed, který je 4.
3. Hodnoty pole menší než střední jsou z vyhledávání vypuštěny a hodnoty větší než střední hodnota 4 jsou prohledávány.
4. 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í?

Z následujících důvodů je binární vyhledávání lepší volbou pro použití jako vyhledávací algoritmus:

• Binární vyhledávání funguje efektivně na setříděných datech bez ohledu na velikost dat
• Namísto 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í porovnávání setříděných dat na principu řazení než pomocí porovnává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.

Naučte se náš další tutoriál Lineární vyhledávání: Python, C++ Příklad

Shrnutí

• Search je nástroj, který umožňuje uživateli vyhledávat dokumenty, soubory a další typy dat. Binární vyhledávání je pokročilý typ vyhledávacího algoritmu, který najde a načte data z setříděného seznamu položek.
• Binární vyhledávání je běžně známé jako polointervalové vyhledávání nebo logaritmické vyhledávání
• Funguje to tak, že pole rozdělí na polovinu při každé iteraci pod požadovaným prvkem.
• Jedno binární algoritmus vezme střed pole vydělením součtu hodnot indexu nejvíce vlevo a vpravo 2. Nyní algoritmus vypustí buď spodní nebo horní mez 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í porovnávání setříděných dat na základě principu řazení než pomocí srovnání rovnosti, která jsou pomalá a nepřesná.
• Binární vyhledávání není vhodné pro netříděná data.