Бинарный поиск

Ищем быстро в отсортированных данных, деля диапазон пополам.

🎣 Hook

Ищешь книгу в алфавитном каталоге: открыл середину, понял в какую половину идти, повторил.

🧠 Concept

Термины: list, dictionary, loop, function — пишем по-английски, объясняем по-русски.

Бинарный поиск работает только на отсортированных данных.
Шаги:
1) взять середину;
2) сравнить с целью;
3) отбросить половину диапазона.

Сложность: O(log n).

🧩 Квиз +10 XP

Главное требование бинарного поиска?

A Список должен быть отсортирован

B Список должен быть коротким

C Нужны только числа

D Нельзя использовать циклы

🔧 Практика

Задание 1: укажи обязательное условие для бинарного поиска.

data = "отсортирован"
print(data)

Заполни пропуски в коде в своей тетради/редакторе. Ключевые ответы: отсортирован.

Задание 2: заполни формулу индекса середины.

mid = (left + right) // 2

Проверь себя: 2.

🧩 Квиз +10 XP

Почему O(log n) быстрее O(n)?

A Потому что делим диапазон пополам

B Потому что код короче

C Потому что меньше памяти

D Потому что Python быстрее

🏗️ Сборка: мини-проект

Напиши функцию binary_search(scores, target) для отсортированного списка уровней игроков.

👹 Мини-босс +120 XP

Комбинируем текущую тему с предыдущими навыками.

A Сделать без структуры, потом чинить

B Сначала план, затем реализация и проверка

C Копировать решение без понимания

D Пропустить тесты ради скорости

💭 Reflection

Ты освоил ускоренный поиск и ключевую идею «уменьшаем задачу вдвое».