Олег Деревенец - Песни о Паскале

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- Результаты исследования алгоритмов поиска

Что вы скажете об этом? Двоичный поиск дал превосходный результат, – любое число находится не более чем за 10 шагов! Это любопытно, и побуждает разобраться в алгоритме глубже.

Принимаясь за что-либо, мы прикидываем, сколько времени займет то или иное дело. Поиск может отнять уйму времени, вот почему важно оценить его трудоемкость. Сравним алгоритмы поиска по затратам времени. Только время будем измерять не секундами, а особыми единицами – шагами поиска. Почему? Да потому, что у нас с вами разные компьютеры. Поскольку ваш «станок» мощнее, ту же работу он выполнит быстрее моего, а это нечестно! Мы ведь алгоритмы сравниваем, а не процессоры.