Войти
Графическое представление таблицы дихотомического поиска: сдвиг влево представляет Dit (.), а сдвиг вправо представляет Dah (-). Место приземления указывает букву кода. | T - | M - - | O - - - | CH - - - - |
| Ö - - - · | |||
| G - - · | Q - - · - | ||
| Z - - · · | |||
| N - · | K - · - | Y - · - - | |
| C - · - · | |||
| D - · · | X - · · - | ||
| B - · · · | |||
| E · | A · - | W · - - | J · - - - |
| P · - - · | |||
| R · - · | Ä · - · - | ||
| L · - · · | |||
| I · · | U · · - | Ü · · - - | |
| F · · - · | |||
| S · · · | V · · · - | ||
| H · · · · |
В информатике дихотомический поиск - это алгоритм поиска, который работает путем выбора между двумя различными альтернативами. (дихотомии) на каждом этапе. Это особый тип алгоритма разделяй и властвуй. Хорошо известным примером является двоичный поиск.
В абстрактном смысле дихотомический поиск можно рассматривать как следующие ребра неявной структуры двоичного дерева до тех пор, пока он не достигнет листа (цели или конечного состояния). Это создает теоретический компромисс между количеством возможных состояний и временем выполнения: при k сравнениях алгоритм может достичь только O (2) возможных состояний и / или возможных целей.
Некоторые дихотомические поиски дают результаты только на листьях дерева, например, дерево Хаффмана, используемое в кодировании Хаффмана, или неявное дерево классификации используется в Двадцать вопросов. Другие дихотомические поиски также дают результаты по крайней мере в некоторых внутренних узлах дерева, таких как таблица дихотомического поиска для азбуки Морзе. Таким образом, в определении есть некоторая расплывчатость. Хотя на самом деле может быть только два пути от любого узла, таким образом, на каждом шаге есть три возможности: выбрать один путь вперед или другой, или «остановиться на этом узле».
Дихотомический поиск часто используется в руководствах по ремонту, иногда графически проиллюстрированный блок-схемой, похожей на дерево отказов.
.
