Бинарный поиск — один из базовых алгоритмов, который должен уверенно знать любой разработчик. Его главная идея: на каждом шаге отбрасывать половину вариантов, если данные упорядочены или ответ можно проверить через условие.
Почему это важно:
- работает за O(log n)
- часто встречается на собеседованиях
- помогает не только искать элемент, но и находить границы, минимум, максимум и оптимальный ответ
Где применяется бинарный поиск
- поиск числа в отсортированном массиве
- поиск первого или последнего вхождения элемента
- нахождение нижней и верхней границы
- поиск ответа по условию: “минимальное значение, при котором функция становится true”
- задачи на оптимизацию: скорость, время, размер, нагрузка ⚙️
Классический шаблон
Есть массив a, и нужно найти x.
- Берём границы:
l = 0,r = n - 1 - Считаем середину:
mid = l + (r - l) / 2 - Сравниваем
a[mid]иx - Если
a[mid] < x— идём вправо - Иначе — влево или фиксируем ответ
Важно: выбор цикла while (l <= r) или while (l < r) зависит от задачи. Ошибки чаще всего возникают именно на границах.
Популярные паттерны
- Exact match
Ищем точное совпадение элемента.
- First True / Last False
Используется, когда есть монотонная функция:
false false false true true true
Нужно найти позицию, где условие впервые стало истинным. Это очень частый шаблон в задачах на ответ по параметру 📈 - Lower Bound / Upper Bound
lower_bound— первый элемент >=xupper_bound— первый элемент >x
Незаменимо для диапазонов и подсчётов.
Типовые задачи
- Найти индекс элемента в отсортированном массиве
- Найти количество вхождений числа
- Найти минимальную скорость, чтобы выполнить работу за
hчасов - Разделить массив на
kчастей с минимальным максимальным суммарным весом - Найти корень, медиану, порог или ближайшее значение 🧠
Частые ошибки
- переполнение при
mid = (l + r) / 2 - неверное обновление
lиr - зацикливание на двух элементах
- применение к данным без монотонности
- путаница между поиском элемента и поиском границы
Как понять, что нужен бинарный поиск
Задайте себе вопрос:
“Можно ли проверить ответ и при этом при увеличении параметра поведение остаётся монотонным?”
Если да — скорее всего, здесь подходит бинарный поиск ✅
Бинарный поиск — это не просто алгоритм поиска в массиве, а универсальный инструмент для задач, где нужно быстро находить границу или оптимальный ответ.
👀 Загляните в подборку каналов про IT — там много полезного по алгоритмам, разработке и карьерному росту.