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

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.

Двоичный поиск

Двоичный поиск заключается в следующем: вычисляется середина массива и элемент x_i, находящийся по найденному адресу, сравнивается с искомым. Если элементы x_i и isk равны, то поиск закончен. Если x_i < isk, то искомый элемент может находиться в последующей x_i части массива, в противном случае поиск надо осуществлять в предшествующей x_i части массива. Такой подход позволяет сократить число просматриваемых элементов в 2 раза. Далее в выделенной части массива также определяется средний элемент, и он сравнивается с искомым. Подобная процедура повторяется до тех пор, пока ни будет найден заданный элемент или пока не совпадут начальный и конечный адрес просматриваемой, на очередном шаге, части массива. Если эти адреса совпадут и к этому моменту элемент не найден, то его в массиве нет. Временная сложность алгоритма двоичного поиска ~ log₂n.