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

Než se naučíme binární vyhledávání, pojďme si vysvětlit, co vyhledávání vlastně je.

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ý vyhledává a načítá data ze seřazeného seznamu položek. Jeho základní princip fungování spočívá v rozdělení dat v seznamu na poloviny, dokud není nalezena požadovaná hodnota a nezobrazena uživateli ve výsledku vyhledávání. Binární vyhledávání je obecně známé jako 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í začíná nalezením prostředního prvku seřazeného pole dat.
• Poté se klíčová hodnota porovná s elementem.
• Pokud je hodnota klíče menší než prostřední prvek, pak vyhledávání analyzuje horní hodnoty prostředního prvku pro porovnání a nalezení shody.
• V případě, že je hodnota klíče větší než hodnota prostředního prvku, pak vyhledávání analyzuje nižší hodnoty prostředního prvku pro porovnání a nalezení shody.

Binární vyhledávací algoritmus (pseudokód)

Binární vyhledávání lze zapsat jako krátkou iterační rutinu. Uchovává dva ukazatele, nízký a vysoký, a zužuje rozsah, dokud není nalezen cíl nebo dokud se rozsah nevyprázdní.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Rutina vrací index cíle v případě úspěchu a -1, pokud hodnota není přítomna. Protože se rozsah při každém průchodu zmenší na polovinu, smyčka proběhne maximálně log₂(n)krát.

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. Vydělíte levou a pravou hodnotu indexu číslem 2. Výsledek je 4.5, ale bereme spodní hodnotu. Střed je tedy 4.
3. Algoritmus odstraní všechny prvky od středu (4) až po nejnižší mez, protože 59 je větší než 24, a nyní v poli zbývá pouze 5 prvků.
4. Nyní je 59 větší než 45 a menší než 63. Prostřední číslo je 7. Hodnota pravého indexu se tedy stává střední -1, což se rovná 6, a hodnota levého indexu zůstává stejná jako předtím, tedy 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í meze je (l + r) / 2 = 4. Hledaná hodnota je větší než střední hodnota, která je 4.
3. Hodnoty pole menší než střední hodnota jsou z vyhledávání vyřazeny a prohledávají se hodnoty větší než střední hodnota 4.
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í?

Následující důvody dělají binární vyhledávání lepší volbou pro použití jako vyhledávací algoritmus:

• Binární vyhledávání funguje efektivně na seřazených datech bez ohledu na jejich velikost.
• 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í seřazených dat na základě principu uspořádání, spíše než použití porovnávání rovnosti, které je pomalejší a většinou nepřesné.
• Po každém cyklu vyhledávání algoritmus rozdělí velikost pole na polovinu; v další iteraci tedy bude fungovat pouze ve zbývající polovině pole.

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

Binární vyhledávání vs. lineární vyhledávání

Binární vyhledávání a lineární vyhledávání jsou dva nejběžnější způsoby, jak najít hodnotu v kolekci. Následující tabulka znázorňuje, jak se liší:

Stručně řečeno, binární vyhledávání je mnohem rychlejší na velkých seřazených datech, zatímco lineární vyhledávání je jednodušší a je jedinou možností, když data nejsou seřazena.

Nejčastější dotazy