Что такое бинарный поиск — и как найти сломавший всё коммит за 10 шагов

Вчера всё работало. Сегодня кнопка «Оплатить» не нажимается. Между «вчера» и «сегодня» — сорок коммитов от тебя и от ИИ-агента.
Проверять их по одному — вечер насмарку. А есть способ найти виновника за шесть проверок. Он называется бинарный поиск, и ты им уже пользовался. Просто не знал, как он называется.
Что такое бинарный поиск
Бинарный поиск — это способ найти нужное в упорядоченном списке, каждый раз отбрасывая половину.
Помнишь игру «угадай число от 1 до 100»? Плохой игрок спрашивает: «Это 1? А 2? А 3?». Хороший спрашивает: «Больше 50?». Ответ «да» — и половина вариантов исчезла. Дальше: «Больше 75?». И так до конца.
Хороший игрок угадывает любое число за 7 вопросов. Плохому может понадобиться сто.
В коде это выглядит так. Есть массив, отсортированный по возрастанию. Смотрим на середину:
- середина равна искомому — нашли;
- искомое меньше — дальше ищем только в левой половине;
- искомое больше — только в правой.
Повторяем, пока не найдём или пока половинки не кончатся.
Почему это так быстро
Каждый шаг делит задачу пополам. А деление пополам очень быстро съедает даже огромные числа.
- 100 элементов — максимум 7 шагов.
- 1 000 — 10 шагов.
- 1 000 000 — 20 шагов.
- Миллиард — около 30.
Обычный перебор в цикле для миллиона может сделать миллион сравнений. Бинарный — двадцать. Добавь ещё миллион элементов — и бинарному понадобится всего один лишний шаг.
Вот почему поиск по базам данных работает мгновенно даже на гигантских таблицах. Индекс в базе устроен по похожему принципу: данные лежат по порядку, и поиск отсекает лишнее большими кусками.
Главное условие: порядок
Бинарный поиск работает только на отсортированных данных. Это не формальность.
Если список перемешан, «искомое меньше середины» ничего не значит. Нужное может оказаться в отброшенной половине. Поиск не упадёт с ошибкой — он просто тихо скажет «не нашёл», хотя элемент там есть.
Это частая ловушка в коде от ИИ. Функция поиска написана верно, а данные пришли с сервера в случайном порядке. Поэтому правило простое: прежде чем искать половинками, убедись, что всё отсортировано по тому же полю, по которому ищешь.
Неожиданно: его очень трудно написать правильно
Идея умещается в одну фразу. А вот код — нет.
Программист Джон Бентли проводил эксперимент: давал профессионалам задачу написать бинарный поиск. По его словам, около 90% решений содержали ошибку. Чаще всего — граница сдвинута на единицу, и поиск зацикливается или пропускает последний элемент.
Хуже того: ошибка была даже в стандартной библиотеке Java. Строчка mid = (low + high) / 2 на очень больших массивах переполняла число и ломала поиск. Баг прожил около девяти лет, пока его не нашли в 2006 году.
Вывод для тебя: не пиши бинарный поиск руками, если есть готовый. Во многих языках он встроен. В Python — модуль bisect. В Java — Arrays.binarySearch. А в JavaScript для обычных задач хватит includes или find — бинарный нужен, когда данных реально много.
Где он тебе пригодится уже сегодня: git bisect
Вернёмся к сломанной кнопке. В Git есть команда, которая делает бинарный поиск по истории коммитов.
- Запускаешь поиск:
git bisect start. - Говоришь, что сейчас сломано:
git bisect bad. - Называешь коммит, где точно работало:
git bisect good a1b2c3d. - Git переключает проект на коммит посередине. Ты проверяешь кнопку и отвечаешь
git bisect goodилиgit bisect bad. - Через несколько ответов Git пишет: «вот первый плохой коммит».
- Возвращаешься обратно:
git bisect reset.
Сорок коммитов — максимум шесть проверок. Тысяча — десять. А если у тебя есть тест, который ловит баг, можно вообще не отвечать руками: git bisect run npm test прогонит всё сам.
Нашёл коммит — дальше смотришь, что именно в нём поменялось, и решаешь: откатить его или исправить.
Тот же приём работает и без Git. Не понимаешь, какая часть кода ломает страницу? Закомментируй половину. Сломалось — виновник в оставшейся. Нет — в закомментированной. Это ручной бинарный поиск, и он почти всегда быстрее, чем гадать.
Чем бинарный поиск отличается от линейного?
Линейный проверяет элементы по очереди, с начала до конца. Бинарный прыгает в середину и отбрасывает половину. Линейному порядок не нужен, бинарному — обязателен.
Если нужно сначала отсортировать, это не медленнее?
Для одного поиска — да, сортировка дороже простого перебора. Бинарный поиск выгоден, когда ищешь много раз по одним и тем же данным: отсортировал один раз — дальше каждый поиск почти бесплатный.
Почему он называется «бинарный»?
От слова «два»: на каждом шаге выбор из двух половин. Ещё его называют двоичным поиском или поиском делением пополам.
Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.





