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 seznamu. O řešení rovnic pojednává článek půlení intervalů.

Binární vyhledávání (nebo také metoda půlení intervalu) je vyhledávací algoritmus na nalezení zadané hodnoty v uspořádaném seznamu (řady) hodnot pomocí zkracování seznamu o polovinu v každém kroku. Binární vyhledávání najde medián, porovná s hledanou hodnotou a na základě výsledku porovnání se rozhodne o pokračování v horní nebo dolní části seznamu a rekurzivně pokračuje od začátku.

Binární vyhledávání je algoritmus s logaritmickou časovou složitostí O(log n). Přesněji, je potřeba 1 + \log_2 N {} iterací na získání výsledku. Je značně rychlejší než lineární vyhledávání, které má časovou složitost O(n). Nicméně vyžaduje, aby data byla setříděna, je tudíž vhodný jen pro určitou množinu problémů. Dá se vyjádřit rekurzivně i iterativně; ve většině programovacích jazyků je však rekurzivní zápis mnohem elegantnější. Iterativní varianta algoritmu je však (díky absenci režie související s voláním funkcí) mírně rychlejší.

Binární vyhledávání je příkladem algoritmu typu rozděl a panuj.

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