Binární vyhledávání: Porovnání verzí
Smazaný obsah Přidaný obsah
m Robot: Přidávám vi:Tìm kiếm nhị phân, sr:Бинарна претрага, ia:Recerca binari; měním ar:ديكوتومية |
m r2.7.2) (Robot: Upravuji hi:द्विआधारी खोज प्रणाली; kosmetické úpravy |
||
Řádek 1:
'''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í [[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 jazyků je však rekurzivní zápis mnohem elegantnější. [[iterace|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 (algoritmus)|rozděl a panuj]].
Řádek 7:
== Implementace ==
Parametry <code>vlevo</code> a <code>vpravo</code> jsou hodnoty <code>0</code> a <code>n-1</code> kde n je počet prvků pole, které se mají v předávaném poli prohledat
<br />
Rekurzivní implementace binárního vyhledávání v jazyce [[Python]]:
Řádek 48:
[[fr:Dichotomie]]
[[he:חיפוש בינארי]]
[[hi:द्विआधारी खोज प्रणाली
[[ia:Recerca binari]]
[[id:Pencarian biner]]
| |||