Дихотомический поиск (поиск элемента в упорядоченном массиве)

Алгоритм дихотомического поиска достаточно прост. Делим массив пополам и определяем в какой из частей может находиться искомый элемент. Поскольку массив упорядочен, то сравнивая искомый элемент со средним элементом массива, легко определить интересующую нас половину. Затем выбранную половину опять делим пополам и определяем в какой половине находится искомый элемент. Этот процесс продолжаем до тех пор, пока не будет найден искомый элемент, либо левая граница нового отрезка не станет больше правой. В последнем случае можно сделать вывод о том, что искомого элемента в массиве нет.

const n = 20; {kоличество элементов в массиве}

var a: array [1..n] of integer; {исходный массив}

i, x, k, m: integer;

left, right, mid: integer: {левая, правая граница и середина}

f: boolean; {отрезка}

begin

write (‘задайте искомый элемент’);

readln (k);

for i: = 1 to n do

readln (a [i]);

{упорядочивание массива по возрастанию}

for i: = 1 to n – 1 do

begin

m: = i;

for j: = i + 1 to n do

if a[j] < a[m] then m: =j;

x: = a[i];

a[i]: = a[m]; a[m]: = x

end;

{поиск элемента}

f: = false; {элемент не найден}

left: = 1; right: = n;

repeat {поиск элемента в части массива от элемента [left] до

элемента [rigth]}

mid: = (left + right) div 2;

if k < a[mid] then right: = mid – 1 {элемент в левой части}

else if k > a[mid] then left: = mid + 1 {элемент в правой части}

else f: = true; {нашли}

else f: = true; {нашли}

until f or (left > rigth);

if f then writeln (‘элемент с номером’, mid: 2, ‘совпадает с

исковым’, k)

else writeln (‘не нашли’);

End.