Пусть дан массив элементов A и ключ b. Для b необходимо найти совпадающий с ним элемент массива А. Линейный поиск подразумевает последовательный просмотр всех элементов массива А в порядке их расположения, пока не найдется элемент равный b. Если заранее неизвестно, имеется данный элемент в массиве или нет, то необходимо следить за тем, чтобы поиск не вышел за границы массива, что достигается использованием стоппера (барьерного элемента). Рассмотрим 2 примера:

{nostopp.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

1)без использования стоппера

const N=10;

type Any=integer;

var A:array[0..N-1] of Any;

      i:integer;

      b:Any;

begin

  writeln('Введите элементы массива:');

  for i:=0 to N-1 do

  readln(A[i]);

  write('Введите ключ:');

  readln(b);

  i:=0;

  while (i<>N) and (A[i]<>b) do

    i:=i+1;

  if i<>N then writeln('Элемент, совпадающий с ключом, найден. Позиция элемента -',i+1)

                       else writeln('Элементов, совпадающих с ключом, нет');

end.

 

{stopp.pas

Сайт Algorithm (http://www.algorithm1.narod.ru/)

Автор проекта: Galina}

2) с использованием стоппера

const N=11;

type Any=integer;

var A:array[0..N] of Any;

  i:integer;

  b:Any;

begin

  writeln('Введите элементы массива:');

  for i:=0 to N-1 do

   readln(A[i]);

  write('Введите ключ:');

  readln(b);

  A[N]:=b; {стоппер}

  i:=0;

  while A[i]<>b do

  i:=i+1;

  if i<>N then writeln('Элемент, совпадающих с ключом, найден. Позиция элемента -',i+1)

              else writeln('Элементов, совпадающих с ключом, нет');

end.

 

     Следует отметить, что в общем случае при линейном поиске среди N элементов требуется в среднем N/2 сравнений в случае успешного поиска и N сравнений в наихудшем случае, и затраты времени для больших массивов поэтому велики.

     Применяется данный алгоритм, если никакой дополнительной информации о данных массива нет.