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