# Binární vyhledávání

### Z Wikipedie, otevřené encyklopedie

Binární vyhledávání (nebo také metoda půlení intervalu) je vyhledávací algoritmus na nalezení zadané hodnoty v uspořádaném seznamu 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 + log2N 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 jazycích je však rekurzivní zápis mnohem elegantnější. Iterativní varianta algoritmu je však (díky absence režije související s voláním funkcí) mírně rychlejší.

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

## [editovat] Implementace

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[střed] == hodnota:
            return True
        if hodnota < seznam[střed]:
            binarySearch(seznam, hodnota, vlevo, střed - 1)
        else:
            binarySearch(seznam, hodnota, střed + 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[střed] == hodnota:
                return True
            if hodnota < seznam[střed]:
                vpravo = střed - 1
            else:
                vlevo = střed + 1
        return False

Citováno z „http://cs.wikipedia.org../../../b/i/n/Bin%C3%A1rn%C3%AD_vyhled%C3%A1v%C3%A1n%C3%AD.html“

Kategorie: Vyhledávací algoritmy

##### Views

- Článek
- Diskuse
- Aktuální verze

##### Hledání

##### V jiných jazycích

- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- Português
- Русский
- Slovenčina
- Українська