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

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

Временная сложность алгоритма двоичного поиска ~ log₂n.

Схема алгоритма двоичного поиска

First - адрес начала просматриваемой части.

Last - адрес конца просматриваемой части

< =

>

Текст программы

Uses crt;

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

isk,i,n,adr,First,Last:integer;

Begin

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

readln(n);

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

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

writeln;

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

readln(isk);

First:=1; Last:=n;

while First <= Last do begin

adr:=(First+Last) div 2;

if isk=X[adr] then

begin writeln('Yes! isk = ',isk,' adr = ',adr);

exit

end

else if isk<X[adr] then Last:=adr-1

else First:=adr+1;

end; writeln(' Not found'); end.