Дихотомический поиск - Dichotomic search - Wikipedia

Графическое представление таблицы дихотомического поиска: сдвиг влево представляет Dit (.), А сдвиг вправо представляет Dah (-). Место приземления указывает букву кода.

Т -	М - -	О - - -	СН - - - -
			Ö - - - ·
		ГРАММ - - ·	Q - - · -
			Z - - · ·
	N - ·	К - · -	Д - · - -
			С - · - ·
		D - · ·	ИКС - · · -
			B - · · ·
E ·	А · -	Вт · - -	J · - - -
			П · - - ·
		Р · - ·	Ä · - · -
			L · - · ·
	Я · ·	U · · -	Ü · · - -
			F · · - ·
		S · · ·	V · · · -
			H · · · ·

В Информатика, а дихотомический поиск это алгоритм поиска который действует путем выбора между двумя различными альтернативами (дихотомиями) на каждом этапе. Это особый вид разделяй и властвуй алгоритм. Хорошо известный пример: бинарный поиск.

Абстрактно дихотомический поиск можно рассматривать как следующие ребра неявного двоичное дерево структура, пока не достигнет листа (цель или конечное состояние). Это создает теоретический компромисс между количеством возможных состояний и временем работы: k сравнений алгоритм может достичь только O (2^k) возможные состояния и / или возможные цели.

Некоторые дихотомические поиски дают результаты только на листьях дерева, например Дерево Хаффмана используется в Кодирование Хаффмана, или неявное дерево классификации используется в Двадцать вопросов. Другие дихотомические поиски также дают результаты по крайней мере в некоторых внутренних узлах дерева, таких как таблица дихотомического поиска для азбука Морзе. Таким образом, в определении есть некоторая расплывчатость. Хотя действительно может быть только два пути от любого узла, таким образом, есть три возможности на каждом этапе: выберите один путь вперед или другой, или остановитесь на этом узле.

Дихотомический поиск часто используется в руководствах по ремонту, иногда графически иллюстрированных блок-схема похожий на дерево отказов.

Рекомендации

• xlinux.nist.gov, Словарь алгоритмов и структур данных: дихотомический поиск