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

Линейный поиск заключается в последовательном сравнении элементов упорядоченного массива Х с искомым значением isk. Поиск в этом случае заканчивается в двух случаях:

1. Очередной элемент массива Х равен искомому значению isk, в этом случае элемент найден.

2. Очередной элемент массива Х больше искомого значения, а так как все последующие элементы также больше isk, то искомого элемента не может быть в Х.

Схема алгоритма линейного поиска

нет да

нет

да

В худшем случае для поиска заданного элемента алгоритмом линейного поиска приходится проводить n сравнений, т.е. временная сложность алгоритма ~ n.

Текст программы линейного поиска

Uses crt;

Var

X:array[1..10000] of integer;

i, n, isk:integer;

Begin

write(' Введите число элементов в массиве - n ');

readln(n);

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

for i:=1 to n do read(X[i]); writeln;

write(' Введите искомое число'); readln(isk);

for i:=1 to n do

if X[i]=isk then

begin

writeln(' Элемент найден по адресу i = ' ,i );

readln; exit

end

else if X[i]>isk then break;

writeln(' Заданного элемента нет');

readln;

End.