Паскаль - массивы. Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.

Const

n=32;

var

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

i, j, k, p, left, right, center:integer;

begin

{ заполнить массив данными }

Randomize;

for i:=1 to n do a[i]:=Random (101) ;

{ отсортировать массив во возрастанию - пузырьковый метод }

for i : = 1 to n-1 do

for j : = 1 to n-i do

if a[j] > a[j+1] then

begin k : = a[j]; a[j] : = a[j+1]; a[j+1] : = k end;

{ тысяча поисков случайных чисел }

k:=0;

for j:=1 to 1000 do

begin

p:=Random (101) ;

{ собственно, двоичный поиск }

left:=1; right:=n;

while left
begin

Inc (k) ;

if (a[left]=p) or (a[right]=p) then left:=right { нашли }

else begin

center: = (left+right) div 2;

if a[center]=p then left:=right { нашли }

else

if a[center]

else right:=center

end

end

end;

Writeln ('Среднее число поисков равно ', k/1000:4:2)

end.

Тестовое решение:

Среднее число поисков равно 4.61