Алгоритмы последовательного поиска

«Начни с начала и продвигайся, пока не найдёшь нужный ключ; тогда остановись». Такая последовательная процедура является очевидным способом поиска; удобно начать наши рассмотрения с неё, так как на ней основаны многие более сложные алгоритмы. Несмотря на свою простоту, последовательный поиск содержит ряд очень интересных идей.

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

Алгоритм S. (Последовательный поиск.) Имеется таблица записей R1,R2,...,Rn, снабженных соответственно ключами K1,K2,...,Kn. Алгоритм предназначен для поиска записи с данным ключом K. Предполагается, что N≥ 1.

S1. Установить i ≤1.

S2. Если K=Ki, алгоритм оканчивается удачно.

S3. Если K<>Ki, увеличить i на 1.

S4.Если i<=N, то вернутся к шагу S2. В противном случае алгоритм оканчивается неудачно.

Алгоритм Q. (Быстрый последовательный поиск.) В отличие от алгоритма здесь ещё предполагается, что в конце файла стоит фиктивная Rn+1 запись.

Q1.Установить i <=1, Kn+1<=K.

Q2.Если K=Ki, то перейти на Q4.

Q3.Увеличить i на 1 и вернутся к шагу Q2.

Q4. Если i<=N, алгоритм оканчивается удачно; в противном случае - неудачно(i=N+1).

Алгоритм T. (Последовательный поиск в упорядоченной таблице.)

Имеется таблица записей R1,R2,...,Rn, причём ключи удовлетворяют неравенствам K1<K2<...<Kn. Алгоритм предназначен для поиска записи с данным ключом K. В целях удобства и увеличения скорости работы предполагается, что в конце таблицы расположена фиктивная запись Rn+1, ключ которой Kn+1= >K.

T1. Установить i <=1.

T2. Если K<=Ki, то перейти на T4.

T3. Увеличить i на 1 и вернутся к шагу T2.

T4. Если K=Ki, то алгоритм оканчивается удачно, в противном случае - неудачно, нужной записи в таблице нет.