Algoritmus binárního vyhledávání - Binary search algorithm
Třída | Algoritmus vyhledávání |
---|---|
Datová struktura | Pole |
Nejhorší výkon | O (log n ) |
Nejlepší výkon | O (1) |
Průměrný výkon | O (log n ) |
Nejhorší prostorová složitost | O (1) |
V informatice je binární vyhledávání , známé také jako vyhledávání v polovičním intervalu , logaritmické vyhledávání nebo binární chop , vyhledávací algoritmus, který najde pozici cílové hodnoty v seřazeném poli . Binární vyhledávání porovnává cílovou hodnotu se středním prvkem pole. Pokud si nejsou rovni, polovina, ve které cíl nemůže ležet, je odstraněna a hledání pokračuje ve zbývající polovině, přičemž se opět vezme střední prvek pro porovnání s cílovou hodnotou a toto se opakuje, dokud není cílová hodnota nalezena. Pokud hledání skončí zbývající polovinou prázdnou, cíl není v poli.
Binární vyhledávání probíhá v logaritmickém čase v nejhorším případě , dělat srovnání, kde je počet prvků v poli. Binární vyhledávání je rychlejší než lineární vyhledávání s výjimkou malých polí. Aby však bylo možné použít binární vyhledávání, musí být pole nejprve seřazeno. Existují specializované datové struktury určené pro rychlé vyhledávání, například hashovací tabulky , které lze prohledávat efektivněji než binární vyhledávání. Binární vyhledávání však lze použít k řešení širšího okruhu problémů, jako je například nalezení dalšího nejmenšího nebo dalšího největšího prvku v poli vzhledem k cíli, i když v poli chybí.
Existuje mnoho variant binárního vyhledávání. Zejména frakční kaskádování zrychluje binární vyhledávání stejné hodnoty ve více polích. Frakční kaskádování efektivně řeší řadu problémů s vyhledáváním ve výpočetní geometrii a v mnoha dalších oblastech. Exponenciální vyhledávání rozšiřuje binární vyhledávání na neomezené seznamy. Tyto binární vyhledávací strom a B-tree datové struktury jsou založeny na binární vyhledávání.
Algoritmus
Binární vyhledávání funguje na tříděných polích. Binární vyhledávání začíná porovnáním prvku uprostřed pole s cílovou hodnotou. Pokud cílová hodnota odpovídá prvku, vrátí se jeho pozice v poli. Pokud je cílová hodnota menší než prvek, hledání pokračuje v dolní polovině pole. Pokud je cílová hodnota větší než prvek, hledání pokračuje v horní polovině pole. Tím algoritmus eliminuje polovinu, ve které cílová hodnota nemůže ležet v každé iteraci.
Postup
Vzhledem k tomu, řadu z prvků s hodnotami či záznamy řazeny tak, aby , a cílová hodnota , následující podprogramu binární hledání najít index v .
- Nastavte na a na .
- Pokud je hledání ukončeno jako neúspěšné.
- Set (poloha středního prvku) na podlahu z , což je největší celé číslo menší než nebo rovné .
- Pokud , nastavte na a přejděte ke kroku 2.
- Pokud , nastavte na a přejděte ke kroku 2.
- Nyní je hledání dokončeno; vrátit se .
Tento iterační postup sleduje hranice vyhledávání pomocí dvou proměnných a . Postup může být vyjádřen v pseudokódu následujícím způsobem, kde názvy a typy proměnných zůstávají stejné jako výše, je funkcí floor a odkazuje na konkrétní hodnotu, která sděluje selhání vyhledávání.
floor
unsuccessful
function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := floor((L + R) / 2) if A[m] < T then L := m + 1 else if A[m] > T then R := m − 1 else: return m return unsuccessful
Alternativně algoritmus může mít strop z . To může změnit výsledek, pokud se cílová hodnota objeví v poli více než jednou.
Alternativní postup
Ve výše uvedeném postupu algoritmus kontroluje, zda je prostřední prvek ( ) roven target ( ) v každé iteraci. Některé implementace tuto kontrolu vynechají během každé iterace. Algoritmus by tuto kontrolu provedl pouze v případě, že je ponechán jeden prvek (kdy ). Výsledkem je rychlejší srovnávací smyčka, protože při jedné iteraci odpadá jedno srovnání. V průměru však vyžaduje ještě jednu iteraci.
Hermann Bottenbruch publikoval první implementaci, která tuto kontrolu vynechala v roce 1962.
- Nastavte na a na .
- Zatímco ,
- Set (poloha středního prvku) na stropu z , což je nejméně celé číslo větší než nebo rovné .
- Pokud , nastavte na .
- Jinak ; nastavit na .
- Nyní je hledání dokončeno. Pokud , vrať se . V opačném případě hledání skončí jako neúspěšné.
Kde ceil
je stropní funkce, pseudokód pro tuto verzi je:
function binary_search_alternative(A, n, T) is L := 0 R := n − 1 while L != R do m := ceil((L + R) / 2) if A[m] > T then R := m − 1 else: L := m if A[L] = T then return L return unsuccessful
Duplicitní prvky
Procedura může vrátit jakýkoli index, jehož prvek se rovná cílové hodnotě, i když jsou v poli duplicitní prvky. Pokud by například bylo hledané pole a cíl byl , pak by bylo správné, aby algoritmus vrátil 4. (index 3) nebo 5. (index 4) prvek. Pravidelný postup by v tomto případě vrátil 4. prvek (index 3). Ne vždy vrací první duplikát (zvažte, který stále vrací 4. prvek). Někdy je však nutné najít prvek zcela vlevo nebo zcela vpravo pro cílovou hodnotu, která je v poli duplikována. Ve výše uvedeném příkladu je 4. prvek úplně vlevo od hodnoty 4, zatímco 5. prvek je úplně vpravo od hodnoty 4. Alternativní postup výše vždy vrátí index prvku zcela vpravo, pokud takový prvek existuje.
Postup při hledání prvku úplně vlevo
Chcete -li najít prvek zcela vlevo, lze použít následující postup:
- Nastavte na a na .
- Zatímco ,
- Set (poloha středního prvku) na podlahu z , což je největší celé číslo menší než nebo rovné .
- Pokud , nastavte na .
- Jinak ; nastavit na .
- Návrat .
If and , then is the leftmost element that equals . Dokonce i když není v poli, je pořadí ze v poli, nebo počet prvků v poli, které jsou menší než .
Kde floor
je funkce floor, pseudokód pro tuto verzi je:
function binary_search_leftmost(A, n, T): L := 0 R := n while L < R: m := floor((L + R) / 2) if A[m] < T: L := m + 1 else: R := m return L
Postup pro nalezení prvku úplně vpravo
K nalezení prvku zcela vpravo lze použít následující postup:
- Nastavte na a na .
- Zatímco ,
- Set (poloha středního prvku) na podlahu z , což je největší celé číslo menší než nebo rovné .
- Pokud , nastavte na .
- Jinak ; nastavit na .
- Návrat .
If and , then is the rightmost element that equals . I když není v poli, je počet prvků v poli, které jsou větší než .
Kde floor
je funkce floor, pseudokód pro tuto verzi je:
function binary_search_rightmost(A, n, T): L := 0 R := n while L < R: m := floor((L + R) / 2) if A[m] > T: R := m else: L := m + 1 return R - 1
Přibližné shody
Výše uvedený postup provádí pouze přesné shody a zjišťuje polohu cílové hodnoty. Je však triviální rozšířit binární vyhledávání k provádění přibližných shod, protože binární vyhledávání funguje na tříděných polích. Binární vyhledávání lze například použít k výpočtu pro danou hodnotu jeho hodnosti (počet menších prvků), předchůdce (další nejmenší prvek), nástupce (další největší prvek) a nejbližší soused . Dotazy na rozsah, které hledají počet prvků mezi dvěma hodnotami, lze provádět pomocí dvou řadových dotazů.
- Dotazy na pořadí lze provádět pomocí postupu pro nalezení prvku zcela vlevo . Procedura vrátí počet prvků menší než cílová hodnota.
- Předchůdcovské dotazy lze provádět s hodnotícími dotazy. Pokud je hodnost cílové hodnoty, je její předchůdce .
- U následných dotazů lze použít postup pro nalezení prvku úplně vpravo . Pokud je výsledkem spuštění procedury pro cílovou hodnotu , pak následník cílové hodnoty je .
- Nejbližší soused cílové hodnoty je buď její předchůdce, nebo nástupce, podle toho, co je bližší.
- Dotazy na rozsah jsou také jednoduché. Jakmile jsou známy hodnoty těchto dvou hodnot, počet prvků, které jsou větší nebo rovny první hodnotě a menší než druhé, je rozdílem mezi těmito dvěma hodnotami. Tento počet lze upravit o jeden nahoru nebo dolů podle toho, zda by měly být koncové body rozsahu považovány za součást rozsahu a zda pole obsahuje položky odpovídající těmto koncovým bodům.
Výkon
Pokud jde o počet srovnání, výkon binárního vyhledávání lze analyzovat zobrazením běhu procedury na binárním stromu. Kořenový uzel stromu je prostředním prvkem pole. Prostřední prvek dolní poloviny je levý podřízený uzel kořene a střední prvek horní poloviny je pravý podřízený uzel kořene. Zbytek stromu je postaven podobným způsobem. Počínaje kořenovým uzlem se prochází levým nebo pravým podstromem v závislosti na tom, zda je cílová hodnota menší nebo větší než uvažovaný uzel.
V nejhorším případě binární vyhledávání provede iterace srovnávací smyčky, kde notace označuje minimální funkci, která poskytuje největší celé číslo menší nebo rovné argumentu, a je binárním logaritmem . Důvodem je, že nejhoršího případu je dosaženo, když vyhledávání dosáhne nejhlubší úrovně stromu, a pro jakékoli binární vyhledávání ve stromu vždy existují úrovně.
K nejhoršímu případu může dojít také tehdy, když cílový prvek není v poli. Pokud je jedna menší než mocnina dvou, je tomu tak vždy. V opačném případě může vyhledávání provádět iterace, pokud vyhledávání dosáhne nejhlubší úrovně stromu. Pokud však hledání skončí na druhé nejhlubší úrovni stromu , může dojít k opakování, což je o jednu méně než v nejhorším případě.
V průměru za předpokladu, že je pravděpodobné, že bude prohledán každý prvek, binární vyhledávání provede iterace, když je cílový prvek v poli. To se přibližně rovná iteracím. Když cílový prvek není v poli, binární vyhledávání provede v průměru iterace za předpokladu, že je stejně pravděpodobné, že bude prohledán rozsah mezi a mimo prvky.
V nejlepším případě, kde je cílová hodnota středním prvkem pole, je jeho pozice vrácena po jedné iteraci.
Pokud jde o iterace, žádný vyhledávací algoritmus, který funguje pouze porovnáváním prvků, nemůže vykazovat lepší průměrný a nejhorší výkon než binární vyhledávání. Porovnávací strom představující binární vyhledávání má nejméně úrovní, protože každá úroveň nad nejnižší úrovní stromu je zcela vyplněna. V opačném případě může vyhledávací algoritmus eliminovat několik prvků v iteraci, což zvyšuje počet požadovaných iterací v průměrném a nejhorším případě. To je případ jiných vyhledávacích algoritmů založených na srovnání, protože i když mohou na některých cílových hodnotách pracovat rychleji, průměrný výkon všech prvků je horší než binární vyhledávání. Rozdělením pole na polovinu zajišťuje binární vyhledávání, aby velikost obou dílčích polí byla co nejpodobnější.
Složitost vesmíru
Binární vyhledávání vyžaduje tři ukazatele na prvky, což mohou být indexy pole nebo ukazatele na umístění v paměti, bez ohledu na velikost pole. Prostorová složitost binárního vyhledávání je tedy ve slově RAM model výpočtu.
Odvození průměrného případu
Průměrný počet iterací provedených binárním vyhledáváním závisí na pravděpodobnosti prohledávání každého prvku. Průměrný případ se liší u úspěšných a neúspěšných vyhledávání. Bude se předpokládat, že každý prvek bude stejně pravděpodobně vyhledáván pro úspěšné vyhledávání. U neúspěšných vyhledávání se bude předpokládat, že stejně pravděpodobně budou prohledávány i intervaly mezi a mimo prvky. Průměrný případ úspěšných vyhledávání je počet iterací potřebných k vyhledání každého prvku přesně jednou, děleno počtem prvků. Průměrný případ neúspěšných vyhledávání je počet iterací potřebných k vyhledání prvku v každém intervalu přesně jednou, děleno intervaly.
Úspěšná vyhledávání
V reprezentaci binárního stromu může být úspěšné hledání reprezentováno cestou od kořene k cílovému uzlu, která se nazývá interní cesta . Délka cesty je počet hran (spojení mezi uzly), kterými cesta prochází. Počet iterací prováděných hledání, vzhledem k tomu, že odpovídající dráha má délku , se počítá počáteční iteraci. Délka vnitřní cesty je součtem délek všech jedinečných vnitřních cest. Protože existuje pouze jedna cesta od kořene k jakémukoli jednotlivému uzlu, každá vnitřní cesta představuje hledání konkrétního prvku. Pokud existují prvky, což je kladné celé číslo, a délka vnitřní cesty je , pak průměrný počet iterací pro úspěšné hledání , přičemž jedna iterace je přidána k počítání počáteční iterace.
Protože je binární vyhledávání optimálním algoritmem pro vyhledávání s porovnáváním, tento problém se redukuje na výpočet minimální délky vnitřní cesty všech binárních stromů s uzly, která se rovná:
Například v poli 7 prvků kořen vyžaduje jednu iteraci, dva prvky pod kořenem vyžadují dvě iterace a čtyři níže uvedené prvky vyžadují tři iterace. V tomto případě je délka vnitřní cesty:
Průměrný počet iterací by byl založen na rovnici pro průměrný případ. Sumu za lze zjednodušit na:
Dosazením rovnice za do rovnice za :
Pro celé číslo je to ekvivalentní rovnici pro průměrný případ úspěšného vyhledávání specifikovaného výše.
Neúspěšná vyhledávání
Neúspěšná hledání mohou být reprezentována rozšířením stromu o externí uzly , které tvoří rozšířený binární strom . Pokud má interní uzel nebo uzel přítomný ve stromu méně než dva podřízené uzly, přidají se další podřízené uzly, nazývané externí uzly, takže každý vnitřní uzel má dvě podřízené uzly. Tím lze neúspěšné hledání reprezentovat jako cestu k externímu uzlu, jehož nadřazený prvek je jediným prvkem, který zůstává během poslední iterace. Vnější cesta je cesta od kořenu k externímu uzlu. Délka vnější cesty je součtem délek všech jedinečných vnějších cest. Pokud existují prvky, což je kladné celé číslo, a délka externí cesty je , pak průměrný počet iterací pro neúspěšné hledání , přičemž jedna iterace je přidána k počítání počáteční iterace. Délka vnější cesty je dělena místo, protože existují externí cesty, které představují intervaly mezi prvky pole a mimo ně.
Tento problém lze podobně omezit na určení minimální délky vnější cesty všech binárních stromů s uzly. U všech binárních stromů je délka vnější cesty stejná jako délka vnitřní cesty plus . Dosazením rovnice za :
Dosazením rovnice za do rovnice za lze určit průměrný případ neúspěšných hledání:
Provedení alternativního postupu
Každá iterace výše definovaného binárního vyhledávacího postupu provede jedno nebo dvě srovnání, přičemž se v každé iteraci zkontroluje, zda se střední prvek rovná cíli. Za předpokladu, že je pravděpodobné, že bude prohledán každý prvek, provede každá iterace v průměru 1,5 srovnání. Variace algoritmu kontroluje, zda se střední prvek na konci vyhledávání rovná cíli. V průměru to eliminuje polovinu srovnání z každé iterace. To mírně zkracuje čas potřebný na iteraci na většině počítačů. Zaručuje však, že hledání zabere maximální počet iterací, v průměru do vyhledávání přidá jednu iteraci. Vzhledem k tomu, že srovnávací smyčka se v nejhorším případě provádí pouze několikrát, mírné zvýšení účinnosti na iteraci nekompenzuje extra iteraci pro všechny, ale velmi velké .
Provozní doba a využití mezipaměti
Při analýze výkonu binárního vyhledávání je dalším faktorem čas potřebný k porovnání dvou prvků. U celých čísel a řetězců se požadovaný čas zvyšuje lineárně s tím, jak se zvyšuje délka kódování (obvykle počet bitů ) prvků. Například srovnání dvojice 64bitových celých čísel bez znaménka by vyžadovalo porovnání až dvojnásobku bitů jako porovnání dvojice 32bitových celých čísel bez znaménka. Nejhoršího případu je dosaženo, když jsou celá čísla stejná. To může být významné, když jsou délky kódování prvků velké, například u velkých celočíselných typů nebo dlouhých řetězců, což činí porovnávání prvků nákladnými. Kromě toho je porovnávání hodnot s plovoucí desetinnou čárkou (nejběžnější digitální reprezentace reálných čísel ) často dražší než porovnávání celých čísel nebo krátkých řetězců.
U většiny počítačových architektur má procesor hardwarovou mezipaměť oddělenou od RAM . Vzhledem k tomu, že jsou umístěny v samotném procesoru, ke cache je přístup mnohem rychlejší, ale obvykle ukládají mnohem méně dat než RAM. Většina procesorů proto ukládá paměťová místa, ke kterým bylo v poslední době přistoupeno, spolu s paměťovými místy blízko ní. Když je například přistupováno k prvku pole, samotný prvek může být uložen společně s prvky, které jsou uloženy blízko něj v paměti RAM, takže je rychlejší sekvenční přístup k prvkům pole, které jsou navzájem blízko v indexu ( referenční lokalita ) . Na tříděném poli může binární vyhledávání přeskočit na vzdálená místa v paměti, pokud je pole velké, na rozdíl od algoritmů (jako je lineární vyhledávání a lineární sondování v tabulkách hash ), které přistupují k prvkům v pořadí. To mírně zvyšuje dobu běhu binárního vyhledávání velkých polí na většině systémů.
Binární vyhledávání versus jiná schémata
Seřazená pole s binárním vyhledáváním jsou velmi neefektivním řešením, když jsou operace vkládání a odstraňování prokládány s načítáním, což si vyžaduje čas na každou takovou operaci. Kromě toho mohou tříděná pole komplikovat využití paměti, zejména když jsou prvky často vkládány do pole. Existují i jiné datové struktury, které podporují mnohem efektivnější vkládání a mazání. Binární vyhledávání lze použít k provedení přesné shody a nastavení členství (určení, zda je cílová hodnota ve sbírce hodnot). Existují datové struktury, které podporují rychlejší přesné párování a nastavují členství. Na rozdíl od mnoha jiných schémat vyhledávání však lze pro efektivní přibližné párování použít binární vyhledávání, které obvykle provádí takové shody včas bez ohledu na typ nebo strukturu samotných hodnot. Kromě toho existují některé operace, například hledání nejmenšího a největšího prvku, které lze efektivně provádět na tříděném poli.
Lineární vyhledávání
Lineární vyhledávání je jednoduchý vyhledávací algoritmus, který kontroluje každý záznam, dokud nenajde cílovou hodnotu. Lineární vyhledávání lze provádět na propojeném seznamu, což umožňuje rychlejší vkládání a mazání než pole. Binární vyhledávání je rychlejší než lineární vyhledávání seřazených polí, kromě případů, kdy je pole krátké, přestože je třeba pole předem seřadit. Všechny algoritmy řazení založené na porovnávacích prvcích, jako je rychlé řazení a sloučení , vyžadují v nejhorším případě alespoň srovnání. Na rozdíl od lineárního vyhledávání lze pro efektivní přibližné párování použít binární vyhledávání. Existují operace, jako je nalezení nejmenšího a největšího prvku, který lze efektivně provést na seřazeném poli, ale ne na netříděném poli.
Stromy
Binární vyhledávací strom je binární strom datová struktura, která funguje na základě principu binárního vyhledávání. Záznamy stromu jsou uspořádány v seřazeném pořadí a každý záznam ve stromu lze vyhledávat pomocí algoritmu podobného binárnímu vyhledávání, přičemž průměrný logaritmický čas trvá. Vkládání a mazání také vyžaduje průměrně logaritmický čas v binárních vyhledávacích stromech. To může být rychlejší než lineární časové vkládání a mazání tříděných polí a binární stromy si zachovávají schopnost provádět všechny možné operace na tříděném poli, včetně rozsahů a přibližných dotazů.
Binární vyhledávání je však pro vyhledávání obvykle efektivnější, protože binární vyhledávací stromy budou s největší pravděpodobností nedokonale vyvážené, což má za následek mírně horší výkon než binární vyhledávání. To platí i pro vyvážené binární vyhledávací stromy , binární vyhledávací stromy, které vyvažují vlastní uzly, protože jen zřídka vytvářejí strom s co nejmenším počtem úrovní. Kromě vyvážených binárních vyhledávacích stromů může být strom velmi nevyvážený s několika vnitřními uzly se dvěma podřízenými, což má za následek průměrnou a nejhorší dobu hledání, která se blíží srovnání. Binární vyhledávací stromy zabírají více místa než tříděná pole.
Binární vyhledávací stromy se hodí k rychlému vyhledávání v externí paměti uložené na pevných discích, protože binární vyhledávací stromy lze efektivně strukturovat v souborových systémech. B-tree zobecňuje tento způsob organizace stromu. B-stromy se často používají k organizaci dlouhodobého úložiště, jako jsou databáze a souborové systémy .
Hashování
Pro implementaci asociativních polí jsou hashovací tabulky , datová struktura, která mapuje klíče na záznamy pomocí hashovací funkce , obecně rychlejší než binární vyhledávání na seřazeném poli záznamů. Většina implementací tabulky hash vyžaduje v průměru pouze amortizovaný konstantní čas. Hashování však není užitečné pro přibližné shody, jako je například výpočet nejbližšího, nejmenšího, největšího a nejbližšího klíče, protože jedinou informací uvedenou při neúspěšném hledání je, že cíl není přítomen v žádném záznamu. Pro takové zápasy je ideální binární vyhledávání, které je provádí v logaritmickém čase. Binární vyhledávání také podporuje přibližné shody. Některé operace, například hledání nejmenšího a největšího prvku, lze provádět efektivně na seřazených polích, ale ne na hashovacích tabulkách.
Nastavit členské algoritmy
Souvisejícím problémem při hledání je nastavení členství . K nastavenému členství lze také použít jakýkoli algoritmus, který vyhledává, například binární vyhledávání. Existují další algoritmy, které jsou konkrétněji vhodné pro členství v sadě. Bitové pole je nejjednodušší, užitečné, když je rozsah klíčů je omezen. Kompaktně ukládá sbírku bitů , přičemž každý bit představuje jeden klíč v rozsahu klíčů. Bitová pole jsou velmi rychlá a vyžadují pouze čas. Pole Judy1 typu Judy efektivně zpracovává 64bitové klíče.
Pro přibližné výsledky, Bloom filtry , další pravděpodobnostní datová struktura založená na hašování, ukládají sadu klíčů kódováním klíčů pomocí bitového pole a více hashovacích funkcí. Bloom filtry jsou ve srovnání s bitovými poli ve většině případů mnohem prostorově efektivnější než bitová pole a nejsou o moc pomalejší: s hash funkcemi vyžadují členské dotazy pouze čas. Filtry Bloom však trpí falešnými poplachy .
Další datové struktury
Existují datové struktury, které se mohou v některých případech zlepšit pro binární vyhledávání pro vyhledávání i další operace dostupné pro tříděná pole. Například vyhledávání, přibližné shody a operace dostupné pro tříděná pole lze provádět efektivněji než binární vyhledávání na specializovaných datových strukturách, jako jsou stromy van Emde Boas , fúzní stromy , pokusy a bitová pole . Tyto specializované datové struktury jsou obvykle pouze rychlejší, protože využívají vlastností klíčů s určitým atributem (obvykle jde o klíče s malými celými čísly), a proto budou pro klíče, které tento atribut postrádají, časově nebo prostorově náročné. Dokud lze klíče objednat, lze tyto operace vždy provádět alespoň efektivně na seřazeném poli bez ohledu na klíče. Některé struktury, jako jsou Judyho pole, používají kombinaci přístupů, aby to zmírnily při zachování efektivity a schopnosti provádět přibližné párování.
Variace
Jednotné binární vyhledávání
Jednotné binární vyhledávání ukládá místo dolní a horní hranice rozdíl v indexu prostředního prvku od aktuální iterace k další iteraci. Vyhledávací tabulky obsahující rozdíly se počítá předem. Pokud je například prohledávané pole [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , prostřední prvek ( ) bude 6 . V tomto případě je prostřední prvek levého dílčího pole ( [1, 2, 3, 4, 5] ) 3 a střední prvek pravého dílčího pole ( [7, 8, 9, 10, 11] ) je 9 . Jednotné binární vyhledávání by ukládalo hodnotu 3, protože oba indexy se liší o 6 o stejnou částku. Aby se zmenšil vyhledávací prostor, algoritmus buď přičte nebo odečte tuto změnu z indexu prostředního prvku. Jednotné binární vyhledávání může být rychlejší v systémech, kde je neefektivní vypočítat střed, například v desítkových počítačích .
Exponenciální hledání
Exponenciální vyhledávání rozšiřuje binární vyhledávání na neomezené seznamy. Začíná to vyhledáním prvního prvku s indexem, který je mocninou dvou a je větší než cílová hodnota. Poté nastaví tento index jako horní mez a přepne na binární vyhledávání. Vyhledávání trvá iterace před spuštěním binárního vyhledávání a nejvýše iterací binárního vyhledávání, kde je pozice cílové hodnoty. Exponenciální vyhledávání funguje na omezených seznamech, ale stane se vylepšením oproti binárnímu vyhledávání, pouze pokud cílová hodnota leží blízko začátku pole.
Interpolační vyhledávání
Místo výpočtu středového bodu interpolační vyhledávání odhaduje polohu cílové hodnoty, přičemž bere v úvahu nejnižší a nejvyšší prvky v poli a také délku pole. Funguje to na základě toho, že střed není v mnoha případech nejlepším odhadem. Pokud se například cílová hodnota blíží nejvyššímu prvku v poli, pravděpodobně se bude nacházet blízko konce pole.
Běžnou interpolační funkcí je lineární interpolace . Pokud je pole, jsou dolní a horní hranice, respektive, a je cíl, pak se odhaduje, že cíl je na cestě mezi a . Když je použita lineární interpolace a distribuce prvků pole je rovnoměrná nebo téměř stejná, interpolační vyhledávání provádí srovnání.
V praxi je interpolační vyhledávání pomalejší než binární vyhledávání malých polí, protože interpolační vyhledávání vyžaduje další výpočet. Jeho časová složitost roste pomaleji než binární vyhledávání, ale to jen kompenzuje extra výpočet pro velká pole.
Frakční kaskádování
Frakční kaskádování je technika, která zrychluje binární vyhledávání stejného prvku ve více tříděných polích. Hledání každého pole samostatně vyžaduje čas, kde je počet polí. Frakční kaskádování toto snižuje tím, že v každém poli ukládá konkrétní informace o každém prvku a jeho poloze v ostatních polích.
Frakční kaskádování bylo původně vyvinuto pro efektivní řešení různých problémů s výpočetní geometrií . Frakční kaskádování bylo uplatněno i jinde, například při dolování dat a směrování internetového protokolu .
Zobecnění na grafy
Binární vyhledávání bylo zobecněno, aby fungovalo na určitých typech grafů, kde je cílová hodnota uložena ve vrcholu místo prvku pole. Binární vyhledávací stromy jsou jednou z takových generalizací - když je dotazován vrchol (uzel) ve stromu, algoritmus se buď dozví, že vrchol je cíl, nebo v jiném podstromu, ve kterém by se cíl nacházel. Toto však lze dále zobecnit jako následuje: vzhledem k neorientovanému, pozitivně váženému grafu a cílovému vrcholu se algoritmus při dotazování na vrchol dozví, že se rovná cíli, nebo mu je přiřazena hrana dopadu, která je na nejkratší cestě z dotazovaného vrcholu do cíle. Standardní algoritmus binárního vyhledávání je jednoduše případ, kdy je grafem cesta. Podobně binární vyhledávací stromy jsou případ, kdy jsou uvedeny okraje k levému nebo pravému podstromu, když je vrchol dotazu nerovný cíli. Pro všechny neorientované, pozitivně vážené grafy existuje algoritmus, který v nejhorším případě vyhledá cílový vrchol v dotazech.
Hlučné binární vyhledávání
Hlučné binární vyhledávací algoritmy řeší případ, kdy algoritmus nemůže spolehlivě porovnávat prvky pole. Pro každou dvojici prvků existuje určitá pravděpodobnost, že algoritmus provede špatné srovnání. Hlučné binární vyhledávání může najít správnou polohu cíle s danou pravděpodobností, která řídí spolehlivost získané pozice. Každá hlučná procedura binárního vyhledávání musí v průměru provést alespoň srovnání, kde je funkce binární entropie a je pravděpodobnost, že procedura získá špatnou pozici. Hlučný problém binárního vyhledávání lze považovat za případ hry Rényi-Ulam , varianty Twenty Questions, kde mohou být odpovědi nesprávné.
Kvantové binární vyhledávání
Klasické počítače jsou při provádění binárního vyhledávání omezeny na nejhorší případ přesně opakování. Kvantové algoritmy pro binární vyhledávání jsou stále omezeny na část dotazů (představujících iterace klasického postupu), ale konstantní faktor je menší než jeden, což zajišťuje nižší časovou složitost na kvantových počítačích . Jakýkoli přesný postup kvantového binárního vyhledávání - tedy postup, který vždy přináší správný výsledek - vyžaduje v nejhorším případě alespoň dotazy, kde je přirozený logaritmus . Existuje přesný postup kvantového binárního vyhledávání, který v nejhorším případě běží v dotazech. Pro srovnání, Groverův algoritmus je optimální kvantový algoritmus pro vyhledávání neuspořádaného seznamu prvků a vyžaduje dotazy.
Dějiny
Myšlenka na seřazení seznamu položek umožňující rychlejší vyhledávání sahá až do starověku. Nejstarší známý příklad byl tablet Inakibit-Anu z Babylonu, který se datuje do c. 200 př . N. L. Tablet obsahoval asi 500 sexuálně malých čísel a jejich vzájemných vztahů seřazených v lexikografickém pořadí , což usnadnilo hledání konkrétního záznamu. Kromě toho bylo na Egejských ostrovech objeveno několik seznamů jmen seřazených podle prvního písmene . Catholicon , latinský slovník dokončený v roce 1286 n. L., Byl prvním dílem, které popisovalo pravidla pro řazení slov podle abecedy, na rozdíl od pouhých několika prvních písmen.
V roce 1946 provedl John Mauchly první zmínku o binárním vyhledávání v rámci Moore School Lectures , klíčového a základního vysokoškolského kurzu v oblasti výpočetní techniky. V roce 1957 William Wesley Peterson publikoval první metodu pro interpolační vyhledávání. Každý publikovaný binární vyhledávací algoritmus fungoval pouze pro pole, jejichž délka je o jednu menší než mocnina dvou, až do roku 1960, kdy Derrick Henry Lehmer publikoval binární vyhledávací algoritmus, který pracoval na všech polích. V roce 1962 Hermann Bottenbruch představil implementaci binárního vyhledávání ALGOL 60, která umístila srovnání za účelem dosažení rovnosti na konec , přičemž průměrný počet iterací se zvýšil o jednu, ale počet srovnání za iteraci se snížil na jednu. Jednotný binární vyhledávání byla vyvinuta AK Chandra z Stanford University v roce 1971. V roce 1986, Bernard Chazelle a Leonidas J. Guibas zaveden frakční řetězení jako metoda pro řešení mnoha problémů v hledání výpočetní geometrie .
Problémy s implementací
Přestože je základní myšlenka binárního vyhledávání poměrně přímočará, detaily mohou být překvapivě složité
Když Jon Bentley přiřadil binární vyhledávání jako problém v kurzu pro profesionální programátory, zjistil, že devadesát procent neposkytlo správné řešení po několika hodinách práce na něm, a to hlavně proto, že nesprávné implementace se nespustily nebo ve vzácných případech vrátily špatnou odpověď okrajové případy . Studie publikovaná v roce 1988 ukazuje, že přesný kód je k dispozici pouze v pěti z dvaceti učebnic. Kromě toho vlastní implementace binárního vyhledávání Bentley, publikovaná v jeho knize Programming Pearls z roku 1986 , obsahovala chybu přetečení, která zůstala nezjištěna více než dvacet let. Programovací jazyk Java implementace knihovny binárního vyhledávání měl stejný přetečení chybu na více než devět let.
V praktické implementaci budou mít proměnné použité k reprezentaci indexů často pevnou velikost (celá čísla), což může mít za následek aritmetické přetečení velmi velkých polí. Pokud je střední bod rozpětí vypočítán jako , pak hodnota může překročit rozsah celých čísel datového typu použitého k uložení středového bodu, i když a jsou v rozsahu. Pokud a nejsou záporné, lze tomu zabránit výpočtem středového bodu jako .
Pokud podmínky výstupu pro smyčku nejsou definovány správně, může dojít k nekonečné smyčce. Jakmile překročí , hledání se nezdařilo a musí sdělit selhání hledání. Kromě toho musí být smyčka ukončena, když je nalezen cílový prvek, nebo v případě implementace, kde je tato kontrola přesunuta na konec, musí být na místě kontroly, zda bylo hledání úspěšné nebo neúspěšné. Bentley zjistil, že většina programátorů, kteří nesprávně implementovali binární vyhledávání, udělala chybu při definování výstupních podmínek.
Podpora knihovny
Standardní knihovny mnoha jazyků zahrnují rutiny binárního vyhledávání:
-
C poskytuje funkci
bsearch()
ve své standardní knihovně , která je obvykle implementována pomocí binárního vyhledávání, ačkoli to oficiální standard nevyžaduje. -
C ++ je standardní šablonová knihovna poskytuje funkce
binary_search()
,lower_bound()
,upper_bound()
aequal_range()
. -
D je standardní knihovna Phobos v
std.range
modulu poskytuje typSortedRange
(vrácenýsort()
aassumeSorted()
funkce) s metodamicontains()
,equaleRange()
,lowerBound()
atrisect()
, které používají binární techniky vyhledávání ve výchozím nastavení pro rozsahy, které nabízejí náhodný přístup. -
COBOL poskytuje
SEARCH ALL
sloveso pro provádění binárních vyhledávání v tabulkách seřazených podle COBOL. -
Go ‚s
sort
standard package knihovna obsahuje funkceSearch
,SearchInts
,SearchFloat64s
aSearchStrings
, což zavést obecné binární vyhledávání, stejně jako konkrétní implementace pro vyhledávání plátků celých čísel, čísel s plovoucí desetinnou čárkou, a řetězce, resp. -
Java nabízí ve třídách a ve standardním balíčku sadu přetížených
binarySearch()
statických metod pro provádění binárních vyhledávání na polích Java , respektive na s.Arrays
Collections
java.util
List
-
Microsoft ‚s .NET Framework 2.0 nabízí statické generické verze binární vyhledávání v jeho sbírce základní třídy. Příkladem může být
System.Array
metodaBinarySearch<T>(T[] array, T value)
. - Pro Objective-C je Kakao rámec poskytuje
NSArray -indexOfObject:inSortedRange:options:usingComparator:
metodu v systému Mac OS X 10.6 nebo novější. Rámec Apple Core Foundation C také obsahujeCFArrayBSearchValues()
funkci. -
bisect
Modul poskytuje Python . -
Třída Ruby 's Array obsahuje
bsearch
metodu s integrovanou přibližnou shodou.
Viz také
- Metoda půlení - Algoritmus pro nalezení nuly funkce - stejná myšlenka použitá pro řešení rovnic v reálných číslech
- Multiplikativní binární vyhledávání - Variace binárního vyhledávání se zjednodušeným výpočtem středového bodu
Poznámky a reference
Tento článek byl předložen WikiJournal of Science k externímu akademickému peer review v roce 2018 ( zprávy recenzentů ). Aktualizovaný obsah byl znovu integrován na stránku Wikipedie pod licencí CC-BY-SA-3.0 ( 2019 ). Zkontrolovaná verze záznamu je: Anthony Lin; a kol. (2. července 2019). „Algoritmus binárního vyhledávání“ (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10,15347/WJS/2019.005 . ISSN 2470-6345 . Wikidata Q81434400 .
Poznámky
Citace
Prameny
- Bentley, Jon (2000). Programovací perly (2. vyd.). Addison-Wesley . ISBN 978-0-201-65788-3.
- Butterfield, Andrew; Ngondi, Gerard E. (2016). Slovník počítačové vědy (7. vydání). Oxford, Velká Británie: Oxford University Press . ISBN 978-0-19-968897-5.
- Chang, Shi-Kuo (2003). Datové struktury a algoritmy . Softwarové inženýrství a znalostní inženýrství . 13 . Singapur: World Scientific . ISBN 978-981-238-348-8.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Úvod do algoritmů (3. vydání). MIT Press a McGraw-Hill. ISBN 978-0-262-03384-8.
- Fitzgerald, Michael (2015). Ruby kapesní reference . Sebastopol, Kalifornie: O'Reilly Media . ISBN 978-1-4919-2601-7.
- Goldman, Sally A .; Goldman, Kenneth J. (2008). Praktický průvodce datovými strukturami a algoritmy využívajícími Javu . Boca Raton, Florida: CRC Press . ISBN 978-1-58488-455-2.
- Kasahara, Masahiro; Morishita, Shinichi (2006). Rozsáhlé zpracování sekvence genomu . Londýn, Velká Británie: Imperial College Press. ISBN 978-1-86094-635-6.
- Knuth, Donald (1997). Základní algoritmy . Umění počítačového programování . 1 (3. vyd.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89683-1.
- Knuth, Donald (1998). Třídění a hledání . Umění počítačového programování . 3 (2. vyd.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89685-5.
- Knuth, Donald (2011). Kombinatorické algoritmy . Umění počítačového programování . 4A (1. vyd.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-03804-0.
- Moffat, Alistair; Turpin, Andrew (2002). Kompresní a kódovací algoritmy . Hamburk, Německo: Kluwer Academic Publishers. doi : 10,1007/978-1-4615-0935-6 . ISBN 978-0-7923-7668-2.
- Sedgewick, Robert ; Wayne, Kevin (2011). Algoritmy (4. vyd.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-57351-3.Zhuštěná webová verze ; knižní verze .
- Stroustrup, Bjarne (2013). Programovací jazyk C ++ (4. vydání). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2.