Линейный (последовательный) поиск

Простейшей формой поиска является линейный или последовательный поиск (serial search). Этот поиск применяется к таблице, которая организована или как массив, или как связанный список. Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр таблицы с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Его алгоритм заключается в следующем:

1) index = -1;

2) i:= 0;

3) если a[i].Кey = ArgSearch, то index:= i и переход к п. 6;

4) если a[i].key <> ArgSearch, то i:= i+1 ;

5) если i <= HighIndex, то переход к п. 3;

6) завершение поиска.

Переменная index (порядковый номер, индекс в векторе а) играет роль указателя на найденную запись. Если после завершения поиска index = -1, то поиск неудачен, если index ¹ -1, то поиск результативен, причем искомая запись есть a[index].

В случае, когда не осуществляется ни вставок, ни удалений, так что поиск осуществляется по всей таблице с постоянным размером N, то число сравнений зависит от того, где в таблице располагается запись с ключом, равным аргументу поиска. Если данная запись является первой в таблице, то выполняется только одно сравнение. Если эта запись является последней в таблице, то необходимо N сравнений. Если равновероятно, что аргумент попадает в любую заданную позицию таблицы, то успешный поиск (в среднем) будет выполняться за (N+1)/2 сравнений, а неуспешный поиск потребует N сравнений. В любом случае число сравнений пропорционально величине N.

Очевидно, приведенный выше алгоритм подразумевает, что поиск ведется по первичному ключу. Если ключ, по которому ведется поиск, является вторичным ключом и заранее неизвестно, сколько записей имеет одинаковое значение ключа, то для нахождения всех записей с ключом, равным аргументу поиска, необходимо просматривать всю таблицу.

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