Записи в файле можно упорядочить, например, по возрастанию или убыванию значения первичного ключа соответственно:
В этом случае можно построить более эффективные алгоритмы поиска, поскольку после сравнения значения
(условие поиска Q:
) со значением ключа
-й записи файла ясно, в какой части файла продолжать поиск [17].
Методы поиска записей в упорядоченном файле различаются друг от друга стратегией выбора очередной записи из файла для выполнения операции сравнения ключа в соответствии с заданным условием Q. Метод бинарного поиска основан на делении интервала поиска пополам.
Поиск по равенству
. Алгоритм поиска заключается в следующем. Файл считают упорядоченным по возрастанию ключа. Сравнивают значения ключа средней записи
, где
со значением
. Если
то поиск удачный и алгоритм заканчивает свою работу. Если
, то для продолжения поиска выбирается средняя запись правой половины файла:
, где
Если
, то для продолжения поиска выбирается средняя запись левой половины файла:
, где
Процесс деления интервала пополам продолжается до тех пор, пока не будет найдена искомая запись (
), либо пока в интервале не останется всего одна запись. Если значение ее ключа не удовлетворяет условию поиска, то поиск неудачный и искомой записи в файле нет.
Бинарный поиск можно выполнять, работая с блоками файла, а не с записями. При считывании блока в оперативную память поиск записи в блоке может быть последовательным. В этом случае в качестве характеристик блока используются граничные значения ключей записей, находящихся в блоке.
Поиск по интервалу значений
. Алгоритм поиска следующий. Вначале выполняется бинарный поиск записи, значение ключа которой удовлетворяет условию
, либо, если такой записи нет в файле, то значение ключа которой является наиболее близким к
по условию
. Далее последовательно читаются записи в блоках файла до тех пор, пока не будет нарушено условие:
