1. Поиск
 

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

При дальнейшем рассмотрении мы исходим из такого принципиального допущения: группа данных, в которой необходимо отыскать заданный элемент, фиксирована. Будем считать, что множество из N элементов задано, скажем, в виде такого массива:
int A[n];

Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход — простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
1. Элемент найден, т. е. а_i = х;
2. Весь массив просмотрен и совпадения не обнаружено.

Это дает нам линейный алгоритм:
i=0;
while ((i<N)&&(A[i]!=x)) i++;

Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т. е. условие, выполняющееся перед каждым увеличением индекса i выглядит так:
(0≤i<N)&(Ak:0≤k<i : a_k!=x).

Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие:
((i=N)OR(a_i=x)) & (A_k:0≤k<i : a_k!=x).

Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т. е. это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.

Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдёт после N шагов.

Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск? Единственная возможность - попытаться упростить само логическое выражение, ведь оно стоит из двух членов. Следовательно, единственный шанс на пути к более простому решению — сформулировать простое условие эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением х. Назовем такой вспомогательный элемент барьером, ведь он охраняет нас от перехода за пределы массива. Теперь массив нужно описан так: int A[n+1], и алгоритм линейного поиска с барьером выглядит следующим образом:
a[N] = x; i = 0;
while (a[i] != х) i++;
Результирующее условие, выведенное из того же инварианта, что и прежде:
(a_i=x) & (A_k:0≤k<i : a_k!=x).

Очевидно, равенство i = N свидетельствует о том, что совпадения (если не счи-тать совпадения с барьером) не было.