Binární vyhledávání

Binární vyhledávání, zvané též vyhledávání půlením intervalu, je vyhledávací algoritmus pro nalezení specifikované hodnoty, popř. vyloučení její přítomnosti, v seřazené sadě prvků, který uspořádání kolekce využívá k určení poloviny úseku, v níž se hledaná hodnota (z titulu setřídění) nemůže vyskytovat, na základě jejího porovnání s prvkem ve středu tohoto úseku, tzn. jeho mediánem, přičemž tento krok se — nepřipadne-li zadaná hodnota na některý medián — rekurzivně opakuje až do zkrácení úseku na nulovou délku. Binární vyhledávání je příkladem algoritmu typu rozděl a panuj.

Algoritmus používá aritmetiku, a proto je pro jeho nasazení nezbytné, aby k prvkům sady bylo možno přistoupit tzv. náhodným způsobem — na základě indexu. Z tohoto důvodu nelze binárně vyhledávat ve spojových seznamech. Vyhovující datovou strukturou je pole.

Časová složitost binárního vyhledávání je logaritmická — $O(\log <!--\; \; -->n)$ —; v nejhorším případě je potřeba ${\log }_2<!--\; \; -->n+1$ iterací. Vyhledávání půlením intervalu je značně rychlejší než lineární vyhledávání, jež má lineární časovou složitost — $O\left(n\right)$. Ve srovnání s binárním vyhledáváním ovšem lineární vyhledávání nepožaduje setřídění ani možnost náhodného přístupu.

Navzdory rekurentní definici lze algoritmus formulovat také iterativně. Zpravidla se tím ztratí na přehlednosti zdrojového kódu, zato však získá na rychlosti práce algoritmu; s voláním podprogramů je totiž spojena režie. Iterativní zápis je optimalizací.

Implementace

Parametry vlevo a vpravo jsou hodnoty 0 a n-1 kde n je počet prvků pole, které se mají v předávaném poli prohledat.
Rekurzivní implementace binárního vyhledávání v jazyce Python 3:

def binarySearch(seznam, hodnota, vlevo, vpravo):
    if vpravo < vlevo:
        return False
    stred = vlevo + int((vpravo - vlevo) / 2)
    if seznam[stred] == hodnota:
        return True
    if hodnota < seznam[stred]:
        return binarySearch(seznam, hodnota, vlevo, stred - 1)
    else:
        return binarySearch(seznam, hodnota, stred + 1, vpravo)

Díky tomu, že rekurzivní volání jsou na konci funkce, je možné tuto implementaci přepsat pouze pomocí cyklu:

def binarySearch(seznam, hodnota, vlevo, vpravo):
    while vlevo <= vpravo:
        stred = vlevo + int((vpravo - vlevo) / 2)
        if seznam[stred] == hodnota:
            return True
        if hodnota < seznam[stred]:
            vpravo = stred - 1
        else:
            vlevo = stred + 1
    return False

Hledání středu je možné zapsat i jako:

stred = int((vpravo + vlevo) / 2)

Tenhle zápis však může v některých jazycích způsobovat známou chybu při vysokých číslech kdy dochází k překročení maximální hodnoty typu integer.^[1]

Reference

Související články

• Asymptotická složitost
• Interpolační vyhledávání — vylepšení binárního vyhledávání pro rovnoměrně rozložená data
• Kolekce (abstraktní datový typ)
• Lineární vyhledávání — jednodušší (základní) vyhledávání
• Medián
• Pole (datová struktura)
• Rekurze
• Rozděl a panuj (algoritmus)

Externí odkazy

• Obrázky, zvuky či videa k tématu binární vyhledávání na Wikimedia Commons

Autoritní data	TDKIV: 000000440