Последовательный поиск

Постановка задачи: пусть дан массив из N элементов. Необходимо определить номер элемента, который обладает определенными свойствами (чаще всего речь идет просто об элементе с определенным значением, равным k), или установить что такого элемента в массиве нет.

Если массив является неупорядоченным, то единственный алгоритм поиска, применимый в этом случае – последовательный. Суть метода – последовательно перебираются все элементы массива, если на каком-то шаге цикла обнаруживается, что массив закончился или обнаруживается искомый элемент, то цикл заканчивается.

Пример фрагмента программы

const

N = 100;

var

a : array[1..N] of integer;

i,k : integer;

begin

{ввод массива, k}

i:=1;

while (i<=N)and(a[i]<>k) do inc(i);

{после окончания цикла i равно номеру искомого элемента, а если элемент не найден, то i=N+1 }

end.

Использование цикла while вместо for обусловлено сокращением количества сравнений, если нужный элемент находится близко к началу массива. В этом случае, как только элемент будет найден, цикл прекратит свою работу.

Возможна следующая оптимизация этого алгоритма. Добавим искомый элемент на N+1 место в массиве и перепишем программу следующим образом:

const

N = 100;

var

a : array[1..N+1] of integer;

i,k : integer;

begin

{ввод массива, k}

a[N+1]:=k;

i:=1;

while (a[i]<>k) do inc(i);

{после окончания цикла i равно номеру искомого элемента}

end.

Очевидно, что при такой модификации элемент будет найден либо в середине массива, либо на в позиции N+1, поэтому проверку на выход за границы массива можно не делать, потому что условие цикла (a[i]<>k) обязательно нарушится еще в границах массива. После отработки этого цикла i равно N+1, если элемента с заданным значением в массиве не найдено, или равно номеру этого элемента.