Линейный поиск с использованием барьера

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

Постараемся оставить в заголовке цикла лишь простое условие а [ i ]<>x. Для этого используем следующий прием. В массив на (n + 1) - e место запишем ископаемый элемент x, который назовем барьерным. Тогда если в процессе работы программы обнаружится такой индекс i, что а [ i ] = x, то элемент будет найден, а если условие a[i] = x выполнится только при i = n + 1, то, значит, интересующего нас элемента в массиве нет. Таким образом, эта часть программы будет выглядеть так:

a [ n + 1 ]: = x; i: = 1;

While a [ i ]<>x Do Inc (i);

При таком способе поиска в случае наличия в массиве нескольких элементов, удовлетворяющих заданному свойству, также будет найден элемент с наименьшим индексом.

Программа линейного поиска с использованием барьера:

program n7;

const n=5;

var a:array[1..n+1] of integer;

{ массив из n элементов целого типа }

x:integer; { искомый элемент целого типа }

i,k:integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n+1 do read(a[i]);

writeln('Введите x');

readln(x);