Binární vyhledávání

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Tento článek pojednává o vyhledávání v datové struktuře. O řešení rovnic pojednává článek půlení intervalů.

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á — —; v nejhorším případě je potřeba 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. 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[editovat | editovat zdroj]

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:

def binarySearch(seznam, hodnota, vlevo, vpravo):
    if vpravo < vlevo:
        return False
    stred = (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 = (vpravo + vlevo) / 2
        if seznam[stred] == hodnota:
            return True
        if hodnota < seznam[stred]:
            vpravo = stred - 1
        else:
            vlevo = stred + 1
    return False

Související články[editovat | editovat zdroj]