Двоичный поиск, или, как его еще называют, бинарный или дихотомический поиск, является одним из самых быстрых. Первое обращение осуществляется к записи, расположенной в середине массива, упорядоченного по возрастанию значений ключей записей. После сравнения ключа записи (К) с аргументом поиска (А) определяется, к какой части массива следует обращаться дальше. Если значение ключа записи больше значения аргумента поиска, то следующее обращение осуществляется к записи, расположенной в середине первой части массива. В противном случае обращение происходит к записи, расположенной в середине второй части массива. Указанная процедура повторяется для 1/4, 1/8, 1/16 т.д. массива до тех пор, пока не будет найдена искомая запись или не станет пустым интервал, в котором осуществляется поиск.
Недостаток метода в том, что между каждыми двумя обращениями необходимо выполнять вычисления для определения адреса или номера следующей записи, которую следует читать.
Чтобы найти нужную запись в массиве из N записей, в среднем требуется [log 2N] - 1 сравнений. В худшем случае понадобится [log 2N] + 1 сравнений.
Блочный поиск состоит в том, что массив, упорядоченный по возрастанию значений ключей записей, разбивается на определенное число блоков. Для поиска потребуется наименьшее время, если число блоков равно 
. Здесь N — общее число записей в массиве. Число записей в блоке при этом также равно .
В процессе поиска аргумент поиска А сравнивается последовательно с последними записями блоков. Если при сравнении оказывается, что значение аргумента поиска А меньше, чем ключ последней записи очередного блока, то ключи всех записей этого блока последовательно сравниваются с А. При нахождении нужной записи она передается на дальнейшую обработку. Если нужная запись не найдена, то в алгоритме можно предусмотреть выдачу сообщения о неудачном окончании поиска. Схема блочного поиска приведена на рис. 12.2.
|
|
Число записей в последнем блоке массива может оказаться не равным числу записей в остальных блоках, поэтому поиск элемента в последнем блоке (его последовательный просмотр) удобно описывать отдельным алгоритмом.
Для нахождения нужной записи требуется 
сравнений. В худшем случае понадобится 2 
сравнений. Худшим окажется тот случай, когда нужная запись оказывается в последнем блоке и занимает в нем первую позицию (при последовательном просмотре этого блока с конца) или последнюю позицию (при последовательном просмотре этого блока с начала). В массиве из 10000 записей при этом потребуется 199 просмотров.
Возможны различные модификации этого алгоритма. Так, очередное обращение может осуществляться не в конец блока, а в его начало, т.е. к его первой записи. Последовательный просмотр текущего блока также возможен с его конца или начала. Ускоренные методы поиска дают хорошие результаты только при последовательном представлении данных и фиксированной длине записей. При использовании для хранения данных связанного представления на вычисление адреса или номера очередной записи необходимо дополнительное время. Ускоренные методы Поиска следует применять лишь к массивам, хранящимся в ОП ЭВМ. При поиске в массивах данных, хранящихся на ВЗУ, между двумя последовательными сравнениями потребуется перемещение носителя или механизма доступа.
Поиск, аналогичный блочному, обеспечивается системой многоуровневого справочника (см. п. 13.3). Однако при этом расходуется дополнительная память для хранения справочника и затрачивается машинное время на его ведение.