ВУЗ:
Составители:
123
Блочный поиск состоит в том, что массив, упорядоченный по воз-
растанию ключей записей, разбивается на определенное число блоков. Для по-
иска в массиве из N записей потребуется наименьшее время, если число блоков
равно N. Число записей в блоке также равно N. Схему блочного поиска ил-
люстрирует рис. 9.2.
Рис. 9.2. Схема блочного поиска
В процессе поиска аргумент поиска А сравнивается последовательно с
последними записями блоков. Если при сравнении оказывается, что А<К, то
ключи всех записей этого блока последовательно сравниваются с А до нахож-
дения нужной записи при А=К. Если нужная запись не найдена,
то в алгоритме
можно предусмотреть выдачу сообщения о неудачном окончании поиска.
Число записей в последнем блоке может отличаться от числа записей в
остальных блоках, поэтому процедуру последовательного просмотра записей
последнего блока удобно описывать отдельным алгоритмом.
Для нахождения нужной записи этим методом требуется N сравнений.
В худшем случае понадобится 2N сравнений.
Поиск
по двоичному дереву. Из рассмотренных выше методов поиска
бинарный – самый быстрый. Однако его применение ограничено только для
упорядоченных массивов фиксированной длины при последовательном пред-
ставлении данных. Кроме того, в процессе поиска необходимо выполнять опре-
деленные вычисления. Следует заметить, что упорядоченные массивы фиксиро-
ванной длины удобны для поиска, но неудобны для
ведения, так как при добав-
лении или удалении записей требуется перезапись всего массива.
Информационный
массив
Запись 1
Запись
N
Искомая запись А=К
3-е об
р
ащение A<K
2-е об
р
ащение A>K
1-е об
р
ащение A>K
Страницы
- « первая
- ‹ предыдущая
- …
- 121
- 122
- 123
- 124
- 125
- …
- следующая ›
- последняя »
