Представь.
Ты открыл книгу на 1000 страниц.
Тебе нужно найти 500 страницу.
Как будешь искать?
❌ Можно листать так:
1...
2...
3...
4...
5...
Это долго.
Но большинство людей делают совсем по-другому.
📖 Они открывают книгу примерно посередине.
Допустим, на 500 странице.
Если нужная страница больше — листают только вторую половину книги.
Если меньше — только первую.
Потом снова открывают середину оставшейся части.
И снова.
И снова.
Каждый раз книга становится в два раза "меньше".
💡 Именно так работает бинарный поиск.
Он не проверяет всё подряд.
Он постоянно говорит:
"Половина мне точно не нужна. Выкидываем её."
Например, нужно найти число 73 в отсортированном списке от 1 до 100.
1️⃣ Смотрим середину → 50
73 больше? Да.
Выкидываем числа 1–50.
2️⃣ Остались 51–100.
Смотрим середину → 75
73 меньше.
Выкидываем 76–100.
3️⃣ Остались 51–74.
Снова середина.
И так ещё несколько раз.
🎯 Уже через несколько шагов мы найдём число 73.
Хоть в списке было 100 элементов.
А если элементов миллион?
😅 Не миллион проверок.
Примерно 20.
Вот почему бинарный поиск считается одним из самых быстрых способов поиска.
⚠️ Но есть одно правило.
Он работает только тогда, когда данные отсортированы.
Если числа стоят как попало:
8, 3, 99, 15, 42...
то делить список пополам бессмысленно — нужное число может оказаться где угодно.
👇 Представь две ситуации.
📚 Искать книгу на полках по алфавиту.
📚 Искать книгу в комнате, где они просто свалены в огромную кучу.
Как думаешь, где ты найдёшь её быстрее? 😄