Binární vyhledávání
Kategorie: Nezařazeno (celkem: 23181 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 12. srpna 2008
- Zobrazeno: 2293×
Příbuzná témata
Binární vyhledávání
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 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
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