Дихотомический поиск

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

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

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Декабрь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

Ссылки [ править ]

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

См. Также [ править ]

Алгоритм двоичного поиска

Внешние ссылки [ править ]

Программа Python для двоичного поиска (рекурсивный и итеративный)
Бинарный поиск

Эта статья по информатике незавершена . Вы можете помочь Википедии, расширив ее .