худшее – на единицу больше.
А как определить логарифмы других чисел, например, числа 50? Поскольку оно лежит между 32 и 64, его логарифм должен быть где-то между 5 и 6? Так оно и есть: логарифм 50 равен приблизительно 5,64 (это я на калькуляторе посчитал). Но, поскольку мы применяем логарифмы для подсчета шагов поиска, то погрешностью в доли шага можно пренебречь. К чему мелочиться? Будем считать, что логарифм числа 50 тоже равен 6. Мало того, назначим это значение логарифма всем числам в промежутке от 33 до 64.
На рис. 93 сопоставлен рост числа с ростом его логарифма. Когда число увеличивается вдвое, его логарифм возрастает лишь на единицу. Вот почему с ростом размера массива время двоичного поиска растет так медленно (что очень радует нас!).
• Компьютерные базы данных (БД) содержат разнородную информацию, отдельные элементы которой связаны общим индексом.
• Поиск в массиве состоит в определении индекса искомого элемента; зная индекс, можно извлечь всю прочую информацию о нужном объекте.
• Для поиска применяют два способа: последовательный перебор и двоичный поиск.
• Последовательный перебор (линейный поиск) очень прост, но время поиска пропорционально размеру массива, что для больших объёмов данных бывает неприемлемо.
• Двоичный поиск очень быстр, – с ростом размера массива затраты времени на поиск растут по логарифмическому закону. Однако, двоичный поиск работает только в отсортированных массивах.
А). Будет ли линейный поиск работать быстрее в сортированном массиве? Проверьте на практике.
Б) Сколько шагов двоичного поиска потребуется в массиве из миллиона элементов? А из миллиарда? Сравните с трудоемкостью линейного поиска.
В) Напишите полицейскую базу данных, содержащую номера автомобилей и сведения о владельцах. Данные должны вводиться из файла, каждая строка которого содержит номер автомобиля и сведения о владельце, например:
123 Горбунков С.С., ул. Тепличная, д. 21, тел. 11-22-33
35 Стелькин И.Н., ул. Тенистая, д. 5, тел. 33-22-11
Примените массивы и учтите опыт обработки классного журнала.
Г) Отсортируйте полицейскую базу данных и напишите программу для двоичного поиска в ней.
Д) Папа Карло опасался Буратино, и прятал спички в сейфе. Код замка из четырех цифр он доверил лишь своему приятелю – честному малому Джузеппе, который не поддавался ни на какие уговоры деревянного мальчишки. Тогда тот пустился на хитрость. Ладно, – предложил Буратино, – не можешь открыть мне код, – не надо. Давай тогда в игру сыграем: я буду спрашивать, а ты отвечай только «да» или «нет». Первый вопрос был таким: код замка больше 5000? Через несколько минут Буратино уже рылся в папином сейфе. Сделайте программу для быстрого угадывания числа методом Буратино. Роль Буратино (угадывающего) должен исполнять компьютер.
Глава 43
Сортировка по-взрослому
Наше новейшее открытие – быстрый, как ракета, двоичный поиск. Но работает он лишь в сортированном массиве. Так в чем вопрос? Разве сортировка «пузырьком» нам не покорилась? Увы! «Пузырек» насколько же нетороплив, насколько и прост. Много ли проку от быстрого поиска, если выигрыш времени съест сортировка? Так ускорим её!
