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

Простейшей формой поиска является линейный или последовательный поиск (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.

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

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

3. Последовательный поиск в упорядоченной таблице

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

a[0].Кey < a[1].Кey < ... < a[HighIndex].Кey, (10.3)

а для вторичных ключей условие упорядоченности выглядит как

a[0].Кey  a[1].Кey  ...  a[HighIndex].Кey, (104)

Тогда последовательный просмотр ключей таблицы следует завершать при выполнении условия

ArgSearch  a[i].Кey для первичных ключей, (10.5)

ArgSearch < a[i].Кey для вторичных ключей, (10.6)

где i  индекс первого встретившегося при последовательном просмотре ключа, для которого выполняется одно из приведенных условий.

В случае, когда поиск ведется по первичному ключу, выполнение строгого равенства в (10.5), т. е. когда ArgSearch = a[i].Кey, означает, что поиск завершается с результативным итогом, index = i. Если же выполняется условие ArgSearch < a[i].Кey, то поиск завершается, он неудачен (поскольку a[i+1].Кey, a[i+2].Кey, …, a[HighIndex].Кey заведомо больше ArgSearch), index = -1.

При поиске по вторичному ключу выполнение условия (10.6) приводит к останову алгоритма. Поскольку, согласно (10.4), при этом возможны совпадения аргумента поиска с несколькими значениями ключа (допустим число таких значений равно m), то записи a[i-m], a[i-m+1], …, a[i-1] являются искомыми записями и поиск – результативен. Если же совпадений до выполнения неравенства (10.6) не произошло, то завершившийся поиск неудачен. В любом случае значения a[i+1].Кey, a[i+2].Кey, …, a[HighIndex].Кey не проверяются на совпадение с аргументом ArgSearch, поскольку они заведомо больше ArgSearch .

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