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 по основанию два». Математики записывают его следующим образом:

Log₂ N

Связь между числом N и его двоичным логарифмом легко проследить на следующих примерах. Слева представлено разложение на множители нескольких чисел, а справа – двоичные логарифмы этих же чисел.

4 = 2 • 2 Log₂ 4 = 2

16 = 2 • 2 • 2 • 2 Log₂ 16 = 4

64 = 2 • 2 • 2 • 2 • 2 • 2 Log₂ 64 = 6

Итак, двоичный логарифм числа равен количеству двоек (ой, нехорошее слово!), перемножаемых для получения этого числа. Например, для получения числа 8 надо перемножить три двойки, и его логарифм равен трем. Кстати, для получения единицы из восьмерки, её тоже «пилят» пополам трижды. Значит, оба способа вычисления логарифма – через умножение, и через деление – равноценны.

Если вы завтра же не забросите программирование, то табл. 8 с логарифмами нескольких чисел ещё пригодится вам.

Табл. 8 – двоичные логарифмы некоторых чисел

N

Log₂ N

N

Log₂ N

N

Log₂ N

N

Log₂ N

2

1

32

5

512

9

8192

13

4

2

64

6

1024

10

16384

14

8

3

128

7

2048

11

32768

15

16

4

256

8

4096

12

65

536

16

По таблице можно оценить как среднее, так и худшее время двоичного поиска: среднее время равно двоичному логарифму от размера массива, а худшее – на единицу больше.

А как определить логарифмы других чисел, например, числа 50? Поскольку оно лежит между 32 и 64, его логарифм должен быть где-то между 5 и 6? Так оно и есть: логарифм 50 равен приблизительно 5,64 (это я на калькуляторе посчитал). Но, поскольку мы применяем логарифмы для подсчета шагов поиска, то погрешностью в доли шага можно пренебречь. К чему мелочиться? Будем считать, что логарифм числа 50 тоже равен 6. Мало того, назначим это значение логарифма всем числам в промежутке от 33 до 64.

На рис. 93 сопоставлен рост числа с ростом его логарифма. Когда число увеличивается вдвое, его логарифм возрастает лишь на единицу. Вот почему с ростом размера массива время двоичного поиска растет так медленно (что очень радует нас!).

Рис.93 – Сравнение времени линейного и двоичного поиска

Итоги

• Компьютерные базы данных (БД) содержат разнородную информацию, отдельные элементы которой связаны общим индексом.

• Поиск в массиве состоит в определении индекса искомого элемента; зная индекс, можно извлечь всю прочую информацию о нужном объекте.

• Для поиска применяют два способа: последовательный перебор и двоичный поиск.

• Последовательный перебор (линейный поиск) очень прост, но время поиска пропорционально размеру массива, что для больших объёмов данных бывает неприемлемо.

• Двоичный поиск очень быстр, – с ростом размера массива затраты времени на поиск растут по логарифмическому закону. Однако, двоичный поиск работает только в отсортированных массивах.

А слабо?

А). Будет ли линейный поиск работать быстрее в сортированном массиве? Проверьте на практике.

Б) Сколько шагов двоичного поиска потребуется в массиве из миллиона элементов? А из миллиарда? Сравните с трудоемкостью линейного поиска.

В) Напишите полицейскую базу данных, содержащую номера автомобилей и сведения о владельцах. Данные должны вводиться из файла, каждая строка которого содержит номер автомобиля и сведения о владельце, например:

123 Горбунков С.С., ул. Тепличная, д. 21, тел. 11-22-33

35 Стелькин И.Н., ул. Тенистая, д. 5, тел. 33-22-11