Binární vyhledávání

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Tento článek je 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 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 způsobuje známou chybu při vysokých číslech kdy dochází k překročení maximální hodnoty typu integer.[1]

Reference[editovat | editovat zdroj]

  1. The curious case of Binary Search — The famous bug that remained undetected for 20 years https://thebittheories.com/the-curious-case-of-binary-search-the-famous-bug-that-remained-undetected-for-20-years-973e89fc212

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