Информационное обеспечение систем управления

       

Бинарный поиск


Записи в файле можно упорядочить, например, по возрастанию или убыванию значения первичного ключа соответственно:

В этом случае можно построить более эффективные алгоритмы поиска, поскольку после сравнения значения

(условие поиска Q:
) со значением ключа
-й записи файла ясно, в какой части файла продолжать поиск [17].

Методы поиска записей в упорядоченном файле различаются друг от друга стратегией выбора очередной записи из файла для выполнения операции сравнения ключа в соответствии с заданным условием Q. Метод бинарного поиска основан на делении интервала поиска пополам.

Поиск по равенству

. Алгоритм поиска заключается в следующем. Файл считают упорядоченным по возрастанию ключа. Сравнивают значения ключа средней записи
, где
со значением
. Если
 то поиск удачный и алгоритм заканчивает свою работу. Если
, то для продолжения поиска выбирается средняя запись правой половины файла:
, где

Если

, то для продолжения поиска выбирается средняя запись левой половины файла:
, где

Процесс деления интервала пополам продолжается до тех пор, пока не будет найдена искомая запись (

), либо пока в интервале не останется всего одна запись. Если значение ее ключа не удовлетворяет условию поиска, то поиск неудачный и искомой записи в файле нет.

Бинарный поиск можно выполнять, работая с блоками файла, а не с записями. При считывании блока в оперативную память поиск записи в блоке может быть последовательным. В этом случае в качестве характеристик блока используются граничные значения ключей записей, находящихся в блоке.

Поиск по интервалу значений

. Алгоритм поиска следующий. Вначале выполняется бинарный поиск записи, значение ключа которой удовлетворяет условию
, либо, если такой записи нет в файле, то значение ключа которой является наиболее близким к
 по условию
. Далее последовательно читаются записи в блоках файла до тех пор, пока не будет нарушено условие:
.



Содержание  Назад  Вперед