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- Результаты исследования алгоритмов поиска
Экспе-римент Искомое число Количество шагов поиска Последовательный поиск Двоичный поиск 1 5026 544 10 2 8528 828 10 3 7397 100 9 4 2061 52 9 5 8227 634 9 6 9043 177 10 7 4257 10 10 8 3397 704 5 9 4021 887 10 10 8715 815 9 11 6811 53 9 12 5959 141 10 13 928 859 7 14 3295 26 10 15 9534 935 10 16 1618 8 6 17 1066 105 8 18 7081 989 10 19 218 290 9 20 6927 952 10 Среднее количество шагов 455 9
Что вы скажете об этом? Двоичный поиск дал превосходный результат, – любое число находится не более чем за 10 шагов! Это любопытно, и побуждает разобраться в алгоритме глубже.
Ах, время, время!Принимаясь за что-либо, мы прикидываем, сколько времени займет то или иное дело. Поиск может отнять уйму времени, вот почему важно оценить его трудоемкость. Сравним алгоритмы поиска по затратам времени. Только время будем измерять не секундами, а особыми единицами – шагами поиска. Почему? Да потому, что у нас с вами разные компьютеры. Поскольку ваш «станок» мощнее, ту же работу он выполнит быстрее моего, а это нечестно! Мы ведь алгоритмы сравниваем, а не процессоры.
Если улыбнется удача, поиск завершится на первом шаге. Иногда – по закону подлости – тратится максимальное число шагов. Но эти крайние случаи – редкость; обычно поиск занимает какое-то промежуточное время, и наш эксперимент подтвердил это. Программистов интересует время поиска в двух случаях: в худшем, и в среднем (то есть, усредненное по многим случаям).
Начнем с линейного поиска. Очевидно, что в массиве из N элементов худшее время поиска составит N шагов. Что касается среднего времени, то чутье подсказывает, что оно составит половину максимального времени, то есть N/2. Судите сами: искомое число с равной вероятностью может оказаться и ближе и дальше середины массива. Табл. 7 подтверждает эту догадку, – среднее количество шагов там составило 455, что очень близко к значению 1000/2.
Теперь рассмотрим двоичный поиск. Вначале оценим худшее время. Рассудим так. Сколько шагов поиска нужно в массиве из одного элемента? Правильно, один. А теперь вспомним, что при двоичном поиске всякий раз отбрасывается половина оставшегося массива. Значит, посчитав, сколько раз число N делится пополам для получения единицы, мы определим максимальное число шагов. Так и поступим; следите, честно ли я «распилил» нашу тысячу.
1. 1000 / 2 = 500
2. 500 / 2 = 250
3. 250 / 2 = 125
4. 125 / 2 = 62
5. 62 / 2 = 31
6. 31 / 2 = 15
7. 15 / 2 = 7
8. 7 / 2 = 3
9. 3 / 2 = 1
При делении я отбрасывал дробную часть, поскольку в двоичном алгоритме так и делается. Всего потребовалось 9 операций деления. Это значит, что максимальное число шагов поиска равно 10 (с учетом поиска в одном оставшемся элементе). Удивительная прозорливость, – ведь наш эксперимент (табл. 7) показал то же самое!
Теперь оценим среднее время двоичного поиска. Думаете, что оно составит 10/2 = 5 шагов? Как бы ни так! Дело в том, что любой алгоритм поиска в среднем исследует половину массива. Двоичный поиск отбрасывает половину массива на первом же шаге. А это значит, что в среднем число шагов будет всего лишь на единицу меньше худшего, то есть 9. Смотрим в табл. 7, – точно! Наша догадка подтвердилась! Таким образом, двоичный поиск не только быстрее линейного, но и более предсказуем: его худшее время почти не отличается от среднего.
Логарифмы? Это просто!Разобравшись с тысячей элементов, оценим трудоемкость двоичного поиска при других размерах массива. Метод оценки остается тем же: делим размер массива пополам до получения единицы.
Для таких вычислений математики придумали особую функцию – логарифм (не путайте её с рифмой, ритмом и алгоритмом!). Логарифмы бывают разные: десятичные, натуральные и прочие. Нам интересен двоичный логарифм, который по-научному называется так: «логарифм числа N по основанию два». Математики записывают его следующим образом:
Log2 N
Связь между числом N и его двоичным логарифмом легко проследить на следующих примерах. Слева представлено разложение на множители нескольких чисел, а справа – двоичные логарифмы этих же чисел.
4 = 2 • 2 Log2 4 = 2
16 = 2 • 2 • 2 • 2 Log2 16 = 4
64 = 2 • 2 • 2 • 2 • 2 • 2 Log2 64 = 6
Итак, двоичный логарифм числа равен количеству двоек (ой, нехорошее слово!), перемножаемых для получения этого числа. Например, для получения числа 8 надо перемножить три двойки, и его логарифм равен трем. Кстати, для получения единицы из восьмерки, её тоже «пилят» пополам трижды. Значит, оба способа вычисления логарифма – через умножение, и через деление – равноценны.
Если вы завтра же не забросите программирование, то табл. 8 с логарифмами нескольких чисел ещё пригодится вам.