Структуры и алгоритмы обработки данных


Линейный поиск


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

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 свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

 




- Начало -  - Назад -  - Вперед -



Книжный магазин