Алгоритмы
Бинарный поиск: деление пополам
Цели урока
- Реализовать бинарный поиск без ошибок
- Понимать инварианты и избегать off-by-one
- Использовать lower_bound/upper_bound
- Применять binary search the answer
Предварительные знания
- Линейный поиск
- Отсортированные массивы
В 1946 году Джон Мочли описал бинарный поиск. Первая корректная реализация появилась только в 1962 году. 90% программистов с первого раза пишут бинарный поиск с ошибками. Цель урока - попасть в оставшиеся 10%.
- git bisect - поиск коммита с багом
- Базы данных - индексы на B-tree
- Сетевые протоколы - TCP congestion control
- Игры - коллизии (spatial partitioning)
История бинарного поиска
Бинарный поиск описан в 1946 году, но первая корректная реализация для всех размеров массивов появилась только в 1962 году (работа Lehmer). Bug с overflow в `(left + right) / 2` обнаружили в Java только в 2006 году - через 9 лет после выхода JDK!
Идея: делим пополам
**Бинарный поиск** работает на отсортированных данных. На каждом шаге отбрасываем половину.
| n | Линейный (avg) | Бинарный (worst) |
|---|---|---|
| 100 | 50 | 7 |
| 1,000 | 500 | 10 |
| 1,000,000 | 500,000 | 20 |
| 1,000,000,000 | 500,000,000 | 30 |
**log₂(10⁹) ≈ 30**. Среди миллиарда элементов найдём нужный за 30 сравнений!
Сколько максимум сравнений нужно для бинарного поиска в массиве из 1024 элементов?
Реализация: осторожно с границами!
**Классическая реализация:**
**Почему `left + (right - left) // 2`?** При больших left и right их сумма может переполниться (в C/C++, Java). В Python нет проблемы, но хорошая привычка.
**Рекурсивная версия:**
**Итеративная версия предпочтительнее:** O(1) память вместо O(log n) для стека рекурсии.
Что будет если написать `while left < right` вместо `while left <= right`?
Off-by-one: классические ошибки
**Бинарный поиск - один из самых error-prone алгоритмов.** Первая правильная реализация была опубликована только через 16 лет после изобретения!
**Инвариант цикла** - способ доказать корректность:
Почему `left = mid` (без +1) может вызвать бесконечный цикл?
Вариации: lower_bound, upper_bound
**Часто нужен не сам элемент, а граница:**
- **lower_bound(x)** - первый элемент ≥ x
- **upper_bound(x)** - первый элемент > x
- **bisect_left** и **bisect_right** в Python
**C++ STL:** `std::lower_bound`, `std::upper_bound` работают идентично.
arr = [1, 2, 2, 2, 3]. Сколько двоек? (через bisect)
Применения бинарного поиска
**Бинарный поиск применим не только к массивам!** Везде, где есть монотонность - можно бинпоиском.
**Паттерн 'Binary Search the Answer':**
**LeetCode:** ~100 задач решаются binary search. Ключевое слово - 'minimum/maximum that satisfies condition'.
Задача: найти минимальную вместимость корабля, чтобы перевезти все посылки за D дней. Это:
Бинарный поиск
- O(log n) для отсортированных данных
- Осторожно с границами: <=, mid±1, overflow
- lower_bound/upper_bound для границ
- Binary search the answer - мощный паттерн
- bisect модуль в Python, STL в C++
Связанные темы
Бинарный поиск - основа многих алгоритмов и структур данных.
- Интерполяционный поиск — O(log log n) для uniform data
- BST — Бинарный поиск в дереве
- Divide & Conquer — Парадигма деления пополам
Связанные уроки
- alg-09-linear-search — Бинарный поиск - улучшение линейного для отсортированных данных: O(log n) вместо O(n) за счёт отбрасывания половины
- alg-11-interpolation — Интерполяционный поиск - следующий шаг: использует значения для угадывания позиции, O(log log n) для равномерных данных
- ds-11-bst — BST - это бинарный поиск, воплощённый в структуре данных: инвариант дерева = инвариант бинарного поиска
- alg-19-divide-conquer — Бинарный поиск - простейший пример Divide & Conquer: делим пространство поиска пополам каждый шаг
- alg-05-merge-sort — Для эффективного бинарного поиска нужны отсортированные данные - Merge Sort как надёжный способ получить их
- aie-10-vector-databases