Раздел предназначен для всех, кто интересуется программированием и тех, кто серьезно подходит к вопросу подготовки к решению олимпиадных задач по программированию. Подход к изложению материала позаимствован из книги Бхаргава А. "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих" - СПб.: Питер, 2017. - 288 с.
На этом шаге рассмотрим пример, который подводит нас к алгоритму бинарного поиска.
Алгоритмом называется набор инструкций для выполнения некоторой задачи.
Рассмотрим пример из жизни. Предположим, Вам нужно найти в словаре определение понятия "Кибернетика". Можно начать с самого начала и перелистывать страницы словаря, пока не доберемся до буквы "К". Но для ускорения поиска лучше раскрыть книгу на середине.
Теперь допустим, что вы регистрируетесь на сайте, вводите логин и пароль. При этом системе необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти в базе данных. Допустим, вы выбрали себе имя пользователя "Kalinka". Система может начать с буквы "А" и проверять все подряд, но разумнее будет начать с середины.
Получили типичную задачу поиска. И во всех этих случаях для решения задачи можно применить один алгоритм: бинарный поиск.
Бинарный поиск - это алгоритм, который на входе получает отсортированный список элементов. Если элемент, который нам нужно найти, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден.
Рассмотрим работу алгоритма бинарного поиска на простом примере. Пусть Вася загадал число от 1 до 100, а Лиза будет это число отгадывать. Лиза должна за наименьшее количество шагов определить загаданное Васей число.
Лиза может последовательно перечислять числа от 1 до 100, и обязательно угадает, только количество шагов при этом, в общем случае, минимальным не будет.
Это пример простого поиска. При каждой догадке исключается только одно число. Если Вася загадал число 99, то, Лизе потребуется 99 попыток, чтобы отгадать его.
Существует другой, более эффективный способ. Начнем с 50.
Мало ... но Лиза только что исключила половину чисел! Теперь она знает, что все числа от 1 до 50 меньше загаданного. Следующая ее попытка: 75.
На этот раз перелет ... Но Лиза снова исключила половину оставшихся чисел! С бинарным поиском Лиза каждый раз будет загадывать число в середине диапазона и исключать половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75).
И вот Лиза угадывает число!!!
Так работает бинарный поиск. И вы узнали свой первый алгоритм! Попробуем поточнее определить, сколько чисел будет исключаться каждый раз.
Какое бы число Вася ни задумал, Лиза гарантированно сможет угадать его не более чем за 7 попыток, потому что с каждой попыткой исключается половина оставшихся чисел!
Итак, бинарный поиск потребует 7 шагов - заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.
На следующем шаге рассмотрим программную реализацию алгоритма бинарного поиска.
