Песни о Паскале

      for j:= 1 to CSize-i do { внутренний цикл }

      if arg[j] > arg[j+1] then begin { обмен местами }

      t:= arg[j]; arg[j]:= arg[j+1]; arg[j+1]:= t;

      end;

end;

      { Функция последовательного поиска (Find Sequence) }

function FindSeq (aNum: integer): integer;

var i: integer;

begin

      FindSeq:= -1;       { если не найдем, результат будет -1 }

      for i:=1 to CSize do begin

      Steps:= Steps+1; { подсчет шагов поиска }

      if aNum= ArrRand[i] then begin

      FindSeq:= i;       { нашли, возвращаем позицию }

      Break;       { выход из цикла }

      end;

      end;

end;

      { Функция двоичного поиска (Find Binary) }

function FindBin (aNum: integer): integer;

var L, M, R : integer;

begin

      FindBin:= -1;

      L:= 1; R:= CSize;

      repeat

      Steps:= Steps+1;       { подсчет шагов поиска }

      M:= (L+R) div 2;

      if aNum= ArrSort[M] then begin

      FindBin:= M;       { нашли ! }

      Break;       { выход из цикла }

      end;

      if aNum > ArrSort[M]

      then L:= M+1

      else R:= M-1;

      until L > R;

end;

      {--- Главная программа ---}

Var i, n, p : integer;       { вспомогательные переменные }

      F: text;       { файл результатов }

begin

      Assign(F,'P_42_1.OUT'); Rewrite(F);

      { Заполняем массив случайными числами }

      for i:=1 to CSize do ArrRand[i]:=1+Random(10000);

      ArrSort:= ArrRand;       { копируем один массив в другой }

      BubbleSort(ArrSort); { сортируем второй массив }

      repeat       { цикл с экспериментами }

      i:= 1+ Random(CSize); { индекс в пределах массива }

      n:= ArrRand[i];       { случайное число из массива }

      Writeln(F,'Искомое число= ', n);

      Steps:=0;       { обнуляем счетчик шагов поиска }

      p:= FindSeq(n);       { последовательный поиск }

      Writeln(F,'Последовательный: ', 'Позиция= ',

      p:3, ' Шагов= ', Steps);

      Steps:=0;       { обнуляем счетчик шагов поиска }

      p:= FindBin(n);       { двоичный поиск }

      Writeln(F,'Двоичный поиск: ', 'Позиция= ',

      p:3, ' Шагов= ', Steps);

      Write('Введите 0 для выхода из цикла '); Readln(n);

      until n=0;

      Close(F);

end.

Вот результаты трех экспериментов.

Искомое число= 5026

Последовательный: Позиция= 544 Шагов= 544

Двоичный поиск: Позиция= 518 Шагов= 10

Искомое число= 8528

Последовательный: Позиция= 828 Шагов= 828

Двоичный поиск: Позиция= 854 Шагов= 10

Искомое число= 7397

Последовательный: Позиция= 100 Шагов= 100

Двоичный поиск: Позиция= 748 Шагов= 9

Я не поленился проделать 20 опытов, результаты которых занес в табл. 7. Среднее число шагов поиска для каждого из методов посчитано мною на калькуляторе и внесено в последнюю строку таблицы.

Табл. 7- Результаты исследования алгоритмов поиска