🔖 Бинарный поиск: как найти иголку в стоге сена за 3 шага
Представьте: вы ищете номер телефона в огромном справочнике на 1000 страниц. Будете листать с первой страницы?
Есть способ лучше! Откройте справочник посередине. Если нужная буква идет после той, что видите — выбросьте левую половину. Если раньше — правую. Повторите с оставшейся частью.
Поздравляю, вы только что изучили бинарный поиск!
🔸Как это работает?
Ищем число 89 в отсортированном массиве:
[12, 25, 38, 47, 56, 89, 97, 108, 234]
Шаг 1: Средний элемент = 56. 56 < 89 → отбрасываем левую половину
Шаг 2: Средний элемент = 97. 97 > 89 → отбрасываем правую половину
Шаг 3: Средний элемент = 89. Найдено! ✅
🔸Эффективность впечатляет:
- Линейный поиск: до 1000 шагов для 1000 элементов
- Бинарный поиск: максимум 10 шагов!
Секрет в том, что каждый шаг вдвое сокращает область поиска.
🔸Важное условие:
Массив обязательно должен быть отсортирован! Иначе алгоритм не работает.
🔸Где применяется:
- Поиск в базах данных
- Автодополнение в поисковиках
- Системы рекомендаций
- Игры (угадайте число!)
📎 Статья
🎙 Новости
📝 База вопросов