Комбинаторные алгоритмы для программистов



             

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


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

z
в интервале, крайними точками которого являются два заданных указателя
l
(для "низа") и
h
(для "верха"). Новый указатель
m
(для "средней точки") устанавливается где-то около середины интервала, и либо
z
с именем в этой ячейке сводит интервал поиска к одному из интервалов
[l,m - 1]
или
[m + 1,h]
. Если интервал становится пустым, поиск завершается безуспешно.

Для получения логарифмического времени поиска существенно устанавливать указатель

m
за время, не зависящее от длины интервала; это требование делает непригодным бинарный поиск на большинстве вспомогательных запоминающих устройств. Требование, чтобы
m
помещалось точно в середине интервала, несущественно, хотя выбор средней точки в качестве
m
обычно дает самый эффективный алгоритм. В некоторых частных случаях полезно разбить интервал на подинтервалы длины
\alpha (h - l + 1)
и
(1 - \alpha )(h - l + 1)
для фиксированного значения
\alpha
, отличного от
\frac{1} {2}
. Когда таблица размещена не последовательно, а хранится в виде списка древовидной структуры, доля
\alpha
должна, вероятно, меняться от интервала к интервалу.

Бинарный поиск по идее прост, но с деталями условия завершения поиска нужно обращаться осторожно. Частные случаи

h - l = 1
и
h - l = 0
требуют пристального внимания в любой программе бинарного поиска. В алгоритме 13.4 эти случаи обрабатываются тем же кодом, что и в общем случае, и поучительно посмотреть, как это делается, проследив за выполнением алгоритма для
n = 2
и
n = 1
.


Алгоритм 13.4. Бинарный поиск имени
z
в таблице
\{ x_1,\ldots,x_n \}
, хранящейся в естественном порядке.

Корректность алгоритма 13.4 следует из утверждения, данного в комментарии в начале тела цикла. Он устанавливает, что если

z

находится где-либо в таблице, то оно должно находиться в интервале

[l,h]
; иначе говоря, при нашем предположении, что имя появляется в таблице не больше одного раза, утверждается, что
z
не встречается ни в интервале
[1,l - 1]
, ни в интервале
[h + 1,n]
.


Содержание  Назад  Вперед