Wikipedie

Binární vyhledávání: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Vaclav.Makes (diskuse | příspěvky)
6 624 editací
přidání sekce související články
JackalND (diskuse | příspěvky)
778 editací
→‎top: Celkové přepracování (úvodu)
Řádek 1:
{{Různé významy|tento=vyhledávání v seznamu|druhý=řešení rovnic|stránka=půlení intervalů}}
'''Binární vyhledávání''', (nebozvané takétéž '''metodavyhledávání půlenípůlením intervalu'''), je [[vyhledávací algoritmus]] napro nalezení zadanéspecifikované hodnoty, popř. vyloučení její přítomnosti, v uspořádanémseřazené sadě prvků, který uspořádání [[seznamKolekce (abstraktní datový typ)|kolekce]]u využívá k určení poloviny úseku, v níž se hledaná hodnota (řadyz titulu setřídění) hodnotnemůže pomocívyskytovat, zkracovánína seznamuzákladě ojejího polovinuporovnání vs každémprvkem kroku.ve Binárnístředu vyhledávánítohoto úseku, tzn. najdejeho [[medián]]em, porovnápřičemž stento hledanoukrok hodnotouse a— nepřipadne-li zadaná hodnota na základěněkterý výsledkumedián porovnání— se[[Rekurze|rekurzivně]] rozhodneopakuje oaž pokračovánído vzkrácení horníúseku nebona dolnínulovou částidélku. seznamuBinární vyhledávání je příkladem algoritmu typu ''[[Rozděl a rekurzivněpanuj pokračuje(algoritmus)|rozděl oda začátkupanuj]]''.
 
[[Algoritmus]] používá [[Aritmetika|aritmetiku]], a proto je pro jeho nasazení nezbytné, aby k prvkům sady bylo možno přistoupit tzv. náhodným způsobem — na základě indexu. Z tohoto důvodu nelze binárně vyhledávat ve [[Lineární seznam|spojových seznamech]]. Vyhovující [[Datová struktura|datovou strukturou]] je [[Pole (datová struktura)|pole]].
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ší.
 
[[Asymptotická složitost#Typické příklady časové složitosti|Časová složitost]] binárního vyhledávání je logaritmická — <math>O(\log n)</math> —; v nejhorším případě je potřeba <math>\log_2 n +1</math> iterací. Vyhledávání půlením intervalu je značně rychlejší než [[lineární vyhledávání]], jež má lineární [[Asymptotická složitost#Typické příklady časové složitosti|časovou složitost]] — <math>O(n)</math>. Ve srovnání s binárním vyhledáváním ovšem lineární vyhledávání nepožaduje setřídění ani možnost náhodného přístupu.
Binární vyhledávání je příkladem algoritmu typu [[rozděl a panuj (algoritmus)|rozděl a panuj]].
 
Navzdory [[Rekurze|rekurentní]] definici lze [[algoritmus]] formulovat také [[Iterace|iterativně]]. Zpravidla se tím ztratí na přehlednosti [[Zdrojový kód|zdrojového kódu]], zato však získá na rychlosti práce algoritmu; s voláním [[Podprogram|podprogramů]] je totiž spojena režie. Iterativní zápis je [[Optimalizace (informatika)|optimalizací]].
 
== Implementace ==
Citováno z „https://cs.wikipedia.org/wiki/Binární_vyhledávání“