Binární vyhledávání: Porovnání verzí
Smazaný obsah Přidaný obsah
m efektivní odstranění onoho záhadného "-" na konci výrazu v <math>; +1 háček; odstranění duplicitního it iw |
m odkaz |
||
Řádek 1:
'''Binární vyhledávání''' 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í [[Asymptotická složitost|O]](log n). Přesněji, je potřeba <math>1 + \log_2 N {}</math> iterací na získání výsledku. Je značně rychlejší než [[lineární vyhledávání]], které má časovou složitost [[Asymptotická 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 [[rekurze|rekurzivně]] i [[iterace|iterativně]]; ve většině programovacích jazycích je však rekurzivní zápis mnohem elegantnější.
| |||