Блочный поиск

Идея данного метода заключается в том, чтобы делить интервал поис-

ка не на два подынтервала, а на несколько. Эти подынтервалы называют-

ся блоками.

Вначале ищется блок, в котором может находиться аргумент поиска,

путем сравнения его с ключами последних записей в блоках. Если A<Ki,

то аргумент поиска А должен находиться (если он вообще есть) в дан-

ном блоке. В этом случае нижняя граница интервала поиска устанавли-

вается на 1-ю запись этого блока, а верхняя граница - на предпоследнюю запись блока. Затем новый интервал поиска снова разбивается на блоки и

т.д.. Если при очередном сравнении A>Ki, то в данном блоке ключа А

нет. Затем сравнивается последний ключ следующего блока и т.д. Наибо-

лее рационально делить интервал поиска, состоящий из N записей, на

блоки из |__| записей.

Структурограмма алгоритма блочного поиска представлена на рис.

Пример.

Характеристики методов поиска (количество сравнений).

Пример общей программы организации телефонного справочника с

сортировкой и каким-либо поиском (например, стр.283 В.Б.Попов

Turbo Pascal для школьников.