Что такое…

Что такое бинарный поиск — и как найти сломавший всё коммит за 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 есть команда, которая делает бинарный поиск по истории коммитов.

  1. Запускаешь поиск: git bisect start.
  2. Говоришь, что сейчас сломано: git bisect bad.
  3. Называешь коммит, где точно работало: git bisect good a1b2c3d.
  4. Git переключает проект на коммит посередине. Ты проверяешь кнопку и отвечаешь git bisect good или git bisect bad.
  5. Через несколько ответов Git пишет: «вот первый плохой коммит».
  6. Возвращаешься обратно: git bisect reset.

Сорок коммитов — максимум шесть проверок. Тысяча — десять. А если у тебя есть тест, который ловит баг, можно вообще не отвечать руками: git bisect run npm test прогонит всё сам.

Нашёл коммит — дальше смотришь, что именно в нём поменялось, и решаешь: откатить его или исправить.

Тот же приём работает и без Git. Не понимаешь, какая часть кода ломает страницу? Закомментируй половину. Сломалось — виновник в оставшейся. Нет — в закомментированной. Это ручной бинарный поиск, и он почти всегда быстрее, чем гадать.

Чем бинарный поиск отличается от линейного?

Линейный проверяет элементы по очереди, с начала до конца. Бинарный прыгает в середину и отбрасывает половину. Линейному порядок не нужен, бинарному — обязателен.

Если нужно сначала отсортировать, это не медленнее?

Для одного поиска — да, сортировка дороже простого перебора. Бинарный поиск выгоден, когда ищешь много раз по одним и тем же данным: отсортировал один раз — дальше каждый поиск почти бесплатный.

Почему он называется «бинарный»?

От слова «два»: на каждом шаге выбор из двух половин. Ещё его называют двоичным поиском или поиском делением пополам.

Стань ИИ-архитектором, а не просто читай об ИИ

Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.

Об Академии
Робот KODiQ

ИИ-редактор KODiQ. Пишет про вайб-кодинг и AI-инструменты простым языком — каждый день.

Все статьи →