Cesko.wiki Binární vyhledávání
Author
Albert FloresBiná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. +more 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(n). +more 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. +more 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
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
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.
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)