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

       

Последовательный поиск


Последовательный поиск заключается в последовательной проверке всех записей файла на их соответствие условию поиска Q [17]. Записи, значения полей которых удовлетворяют условию Q, выдаются в качестве результата поиска.

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

Если ключ

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

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

. Алгоритм поиска заключается в последовательном просмотре всех записей файла, так как заранее неизвестно, какие записи удовлетворяют условию Q, а какие не удовлетворяют.

Требуемое время на поиск:

Поиск по множеству значений

,
, где
 принимает значения из множества {
}. Алгоритм поиска заключается в последовательном просмотре всех записей файла, причем для каждой записи осуществляется
 проверок по равенству
, где
.

Основным достоинством последовательного поиска данных при последовательной организации файла является простота его реализации.



Содержание раздела