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

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

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

(условие поиска Q:

) со значением ключа

-й записи файла ясно, в какой части файла продолжать поиск [17].

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

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

. Алгоритм поиска заключается в следующем. Файл считают упорядоченным по возрастанию ключа. Сравнивают значения ключа средней записи

, где

со значением

. Если

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

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

, где

Если

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

, где

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

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

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

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

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

, либо, если такой записи нет в файле, то значение ключа которой является наиболее близким к

по условию

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

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