Бинарный поиск

Наиболее эффективным методом поиска в упорядоченном массиве без использования вспомогательных индексов или таблиц является двоичный или бинарный поиск (binary search). Очевидно, что других способов убыстрения поиска не существует, если, конечно, нет еще какой-либо информации о данных, среди которых идет поиск. Другие названия бинарного поиска - поиск делением пополам, дихотомический поиск (dichotomizing search).

Рассмотрим алгоритм бинарного поиска в предположении, что поиск выполняется по первичному ключу. Основная идея - выбрать случайно некоторый элемент, предположим а[m], и сравнить его значение ключа с аргументом поиска ArgSearch. Если а[m].Кey равен ArgSearch, то поиск заканчивается, если он (ключ а[m].Кey ) меньше ArgSearch, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска. Если же он больше ArgSearch, то исключаются индексы больше и равные m. Это соображение приводит нас к алгоритму, программный текст которого приведен ниже. Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.

L:= 0; R:= HighIndex; index:= -1;

While (L<=R) Do

Begin

m:= <любое значение между L и R>;

If а[m].Кey = ArgSearch Then Begin

index:= m;

Break

End

ElseIf a[m].Кey < ArgSearch Then L:= m+1

Else R:= m-1

End;

Выбор m произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шаге из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор срединного элемента (т. е. среднего элемента не по значению, а по положению), для чего в вышеприведенном фрагменте следует записать

m:= (L+R) div 2;

При этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно значению log₂N, округленному до ближайшего целого. Приведенный алгоритм существенно выигрывает по сравнению с последовательным поиском, ведь там ожидаемое среднее число сравнений равно N/2.

Бинарный поиск может быть использован вместе с индексно-последовательной организацией таблицы, упоминавшейся ранее. Вместо поиска по индексу последовательно может быть использован бинарный поиск. Бинарный поиск может быть также использован при поиске в основной таблице, когда идентифицированы две граничные записи. Однако размер этого сегмента таблицы, вероятно, будет настолько малым, что бинарный поиск не более эффективен, чем последовательный поиск.

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