Dikotomisk søk ​​- Dichotomic search

En grafisk fremstilling av den dikotomiske søketabellen for morsekode: Skift til venstre representerer et Dit (.), Og et skifte til høyre representerer en Dah (-). Hvor en lander angir bokstaven for koden.

T -	M - -	O - - -	CH - - - -
			Ö - - - ·
		G - - ·	Q - - · - -
			Z - - · ·
	N - ·	K - · -	Y - · - -
			C - · - ·
		D - · · ·	X - · · - -
			B - · · · ·
E ·	A · -	W · - -	J · - - -
			P · - - ·
		R · - ·	Ä · - · -
			L · - · ·
	JEG · ·	U · · -	Ü · · - -
			F · · - ·
		S · · ·	V · · · -
			H · · · ·

I informatikk er et dikotomisk søk en søkealgoritme som opererer ved å velge mellom to forskjellige alternativer (dikotomier) ved hvert trinn. Det er en spesifikk type dele og erobre -algoritme . Et velkjent eksempel er binært søk .

Abstrakt kan et dikotomisk søk ​​sees på som følgende kanter på en implisitt binær trestruktur til det når et blad (et mål eller en endelig tilstand). Dette skaper en teoretisk avveining mellom antall mulige tilstander og kjøretiden: gitt k sammenligninger kan algoritmen bare nå O (2 ^k ) mulige tilstander og/eller mulige mål.

Noen dikotomiske søk har bare resultater på bladene på treet, for eksempel Huffman -treet som ble brukt i Huffman -koding , eller det implisitte klassifiseringstreet som ble brukt i tjue spørsmål . Andre dikotomiske søk har også resultater i minst noen interne noder i treet, for eksempel en dikotomisk søketabell for morsekode . Det er dermed en del løshet i definisjonen. Selv om det faktisk bare kan være to stier fra en hvilken som helst node, er det således tre muligheter ved hvert trinn: velg den ene eller den andre banen, eller 'stopp ved denne noden.

Dikotomiske søk brukes ofte i reparasjonsmanualer, noen ganger grafisk illustrert med et flytdiagram som ligner et feiltre .

Se også

• Binær søkealgoritme

Referanser

Eksterne linker

• Python -program for binært søk (rekursivt og iterativt)
• Binær søk

Denne informatikkartikkelen er en stubbe . Du kan hjelpe Wikipedia ved å utvide den .

• v
• t
• e