Dichotomické vyhledávání - Dichotomic search - Wikipedia

Grafické znázornění tabulky dichotomického vyhledávání: Posun doleva představuje Dit (.) A posun doprava představuje Dah (-). Kde jeden přistane, označuje písmeno kódu.
T - M - - O - - - CH - - - -
Ö - - - ·
G - - · Q - - · -
Z - - · ·
N - · K - · - Y - · - -
C - · - ·
D - · · X - · · -
B - · · ·
E · A · - W · - - J · - - -
P · - - ·
R · - · Ä · - · -
L · - · ·
Já · · U · · - Ü · · - -
F · · - ·
· · · V · · · -
H · · · ·

v počítačová věda, a dichotomické vyhledávání je vyhledávací algoritmus který funguje výběrem mezi dvěma odlišnými alternativami (dichotomie) v každém kroku. Jedná se o specifický typ algoritmus rozděl a panuj. Známým příkladem je binární vyhledávání.

Abstraktně lze na dichotomické vyhledávání pohlížet jako na následující implicitní okraje binární strom strukturu, dokud nedosáhne listu (cíle nebo konečného stavu). Tím se vytvoří teoretický kompromis mezi počtem možných stavů a ​​dobou chodu: daný k při srovnání může algoritmus dosáhnout pouze O (2k) možné stavy a / nebo možné cíle.

Některá dichotomická vyhledávání mají výsledky pouze u listů stromu, například Huffmanův strom použito v Huffmanovo kódování nebo implicitní klasifikační strom použito v Dvacet otázek. Další dichotomická vyhledávání mají také výsledky alespoň v některých vnitřních uzlech stromu, jako je například dichotomická vyhledávací tabulka pro Morseova abeceda. V definici je tedy určitá volnost. Ačkoli z jakéhokoli uzlu mohou skutečně existovat pouze dvě cesty, existují tři možnosti v každém kroku: vyberte jednu nebo druhou cestu, nebo „zastavte se v tomto uzlu.

Dichotomická vyhledávání se často používají v příručkách k opravám, někdy jsou graficky znázorněna znakem vývojový diagram podobný a strom poruch.

Reference

  • xlinux.nist.gov, Slovník algoritmů a datových struktur: Dichotomické vyhledávání