Что это
Когда ищешь слово в бумажном словаре, ты не листаешь с первой страницы, а открываешь где-то посередине и смотришь, дальше нужное слово или раньше. Так работает бинарный поиск. А если книги на полке стоят как попало, остаётся проверять их по одной — это линейный поиск.
Зачем это нужно
Поиск — одна из самых частых задач компьютера: найти контакт в телефоне, товар среди миллионов в интернет-магазине, нужную запись в базе данных банка или больницы. Поисковые системы вроде Гугла и базы данных в дата-центрах справляются с огромными объёмами информации именно потому, что используют умные алгоритмы, а не простой перебор. ИИ может написать код поиска за секунду, но выбрать подходящий алгоритм, понять, почему программа тормозит на миллионе записей, и проверить её на неудобных случаях — работа человека. Понимание того, как быстро растёт число шагов, отличает инженера от того, кто просто копирует код.
Как это работает
Данные лежат в списке, и у каждого элемента есть номер — индекс; в Питоне индексы начинаются с нуля. Линейный поиск проверяет элементы по очереди и работает с любым списком, но в худшем случае делает столько сравнений, сколько элементов в списке. Бинарный поиск работает только с упорядоченным списком: он смотрит на средний элемент и, если тот меньше искомого, отбрасывает всю левую половину, а если больше — правую. Каждое сравнение делит зону поиска пополам, поэтому даже среди миллиона элементов хватает примерно двадцати шагов.
Немного истории
Идею бинарного поиска описал ещё в 1946 году Джон Мокли, один из создателей первых электронных компьютеров. Идея кажется простой, но написать её без ошибок удивительно трудно: известный программист Дональд Кнут отмечал, что первая полностью правильная опубликованная версия появилась лишь спустя много лет. А в стандартной библиотеке языка Джава ошибку в бинарном поиске нашли только через годы после выпуска.
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Перед тобой пятнадцать карточек с индексами от нуля до четырнадцати; числа на них скрыты, но ты знаешь, что они идут по возрастанию. Загадано число семьдесят, и найти его нужно, открыв не больше четырёх карточек. Открывать по порядку слева — верный способ не уложиться, поэтому каждый раз спрашивай себя: какая карточка стоит в середине зоны поиска и что следует из сравнения её числа с семьюдесятью? После каждого открытия отбрасывай половину, которая точно не подходит, и смотри, как сужается зона. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.