Question

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

Answer 1

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<right do
    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]<p then left:=center+1
          else right:=center
      end
    end
  end;
  Writeln('Среднее число поисков равно ',k/1000:4:2)
end.

Тестовое решение:
Среднее число поисков равно 4.61