![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Блочный поиск
Идея данного метода заключается в том, чтобы делить интервал поис- ка не на два подынтервала, а на несколько. Эти подынтервалы называют- ся блоками. Вначале ищется блок, в котором может находиться аргумент поиска, путем сравнения его с ключами последних записей в блоках. Если A< Ki, то аргумент поиска А должен находиться (если он вообще есть) в дан- ном блоке. В этом случае нижняя граница интервала поиска устанавли- вается на 1-ю запись этого блока, а верхняя граница - на предпоследнюю запись блока. Затем новый интервал поиска снова разбивается на блоки и т.д.. Если при очередном сравнении A> Ki, то в данном блоке ключа А нет. Затем сравнивается последний ключ следующего блока и т.д. Наибо- лее рационально делить интервал поиска, состоящий из N записей, на блоки из |_ Структурограмма алгоритма блочного поиска представлена на рис.
Пример.
Характеристики методов поиска (количество сравнений).
Пример общей программы организации телефонного справочника с сортировкой и каким-либо поиском (например, стр.283 В.Б.Попов Turbo Pascal для школьников.
|