Идея данного метода заключается в том, чтобы делить интервал поис-
ка не на два подынтервала, а на несколько. Эти подынтервалы называют-
ся блоками.
Вначале ищется блок, в котором может находиться аргумент поиска,
путем сравнения его с ключами последних записей в блоках. Если A<Ki,
то аргумент поиска А должен находиться (если он вообще есть) в дан-
ном блоке. В этом случае нижняя граница интервала поиска устанавли-
вается на 1-ю запись этого блока, а верхняя граница - на предпоследнюю запись блока. Затем новый интервал поиска снова разбивается на блоки и
т.д.. Если при очередном сравнении A>Ki, то в данном блоке ключа А
нет. Затем сравнивается последний ключ следующего блока и т.д. Наибо-
лее рационально делить интервал поиска, состоящий из N записей, на
блоки из |_
_| записей.
Структурограмма алгоритма блочного поиска представлена на рис.
Пример.
Характеристики методов поиска (количество сравнений).
| Метод
| Среднее
| Максимальное
|
| Последовательный
| N
| N
|
| Послед. в упорядочен.
| 0.5 * N
| N
|
| Фибоначии
| Log2N
| 1.35*Log2N
|
| Бинарный
| Log2(N-1)
| Log2N
|
| Интерполяционный
| Log2Log2N
| Log2N
|
7. Единая система программной документации.
