Линейный поиск
Если нет никакой дополнительной информации о разыскиваемых данных, то очевидный подход - простой последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено. Такой метод называется линейным поиском. Условия окончания поиска таковы:
1. Элемент найден, т.е. ai = x.
2. Весь массив просмотрен и совпадения не обнаружено.
Это дает нам линейный алгоритм:
i := 0;
WHILE (i < N) AND (a[i] <> x) DO
i := i+1 ;
END;
Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:
(0 £ i < N) AND (Ak : 0 £ k < i : ak ¹ x)
Он говорит, что для всех значений k, меньших чем i, совпадения не было. Отсюда и из того факта, что поиск заканчивается только в случае ложности условия в заголовке цикла, можно вывести окончательное условие:
((i = N) OR (ai = x)) AND (Ak : 0 £ k < i : ak ¹ x)
Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.
Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.
Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск ?
Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент "барьером", ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так:
a: ARRAY[0..N] OF INTEGER
и алгоритм линейного поиска с барьером выглядит следующим образом:
a[N] := x;
i := 0;
WHILE a[i] <> x DO
i := i+1;
END;
Результирующее условие, выведенное из того же инварианта, что и прежде:
(ai=x) AND (Ak : 0 £ k < i : ak ¹ x)
Ясно, что равенство i = N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.
