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

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

, где

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

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

Если ключ

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

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

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

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

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

, где

принимает значения из множества {

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

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

, где

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

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