Когда ячейки таблицы последовательно распределены в памяти с произвольным доступом и имена хранятся в таблице в их естественном порядке, возможен бинарный поиск - один из наиболее широко используемых методов поиска. Идея этого метода состоит в том, чтобы искать имя
в интервале, крайними точками которого являются два заданных указателя
(для "низа") и
(для "верха"). Новый указатель
(для "средней точки") устанавливается где-то около середины интервала, и либо
с именем в этой ячейке сводит интервал поиска к одному из интервалов
или
. Если интервал становится пустым, поиск завершается безуспешно.
Для получения логарифмического времени поиска существенно устанавливать указатель
за время, не зависящее от длины интервала; это требование делает непригодным бинарный поиск на большинстве вспомогательных запоминающих устройств. Требование, чтобы
помещалось точно в середине интервала, несущественно, хотя выбор средней точки в качестве
обычно дает самый эффективный алгоритм. В некоторых частных случаях полезно разбить интервал на подинтервалы длины
и
для фиксированного значения
, отличного от
. Когда таблица размещена не последовательно, а хранится в виде списка древовидной структуры, доля
должна, вероятно, меняться от интервала к интервалу.
Бинарный поиск по идее прост, но с деталями условия завершения поиска нужно обращаться осторожно. Частные случаи
и
требуют пристального внимания в любой программе бинарного поиска. В алгоритме 13.4 эти случаи обрабатываются тем же кодом, что и в общем случае, и поучительно посмотреть, как это делается, проследив за выполнением алгоритма для
и
.
Алгоритм 13.4. Бинарный поиск имени
в таблице
, хранящейся в естественном порядке.
Корректность алгоритма 13.4 следует из утверждения, данного в комментарии в начале тела цикла. Он устанавливает, что если
находится где-либо в таблице, то оно должно находиться в интервале
; иначе говоря, при нашем предположении, что имя появляется в таблице не больше одного раза, утверждается, что
не встречается ни в интервале
, ни в интервале
.
Это утверждение очевидно первый раз,
Комбинаторные алгоритмы для программистов
Это утверждение очевидно первый раз,
Это утверждение очевидно первый раз, когда мы входим в цикл при
и
, и непосредственно по индукции проверяется, что оно выполняется при каждом проходе через цикл. Когда мы выходим из цикла, то должно быть
