TwiddleLab / Код / Как думает программист
Быстрый поиск
Что ты узнаешь
- Двоичный поиск проверяет середину отсортированного списка и выбрасывает половину, где ответа быть не может.
- Каждая проверка делит пополам то, что осталось, поэтому для 100 элементов хватит 7 проверок, а для миллиарда 30.
- mid = (low + high) // 2: // делит и отбрасывает остаток. % даёт сам остаток.
Как идёт урок
Загадано число от 1 до 100.
После каждой догадки звучит «больше» или «меньше». За сколько догадок его всегда можно найти?
Игра: 100 дверей, одно сокровище. Уложись в 7.
Нажми на дверь. Датчик робота говорит «левее» или «правее», и ненужная половина гаснет.
Два робота ищут дверь 73.
Запусти обоих и нажми на робота, которого отправишь в следующий раз.
У деления пополам есть имя и строка кода.
Двоичный поиск находит что-то в отсортированном списке: проверяет середину и выбрасывает половину, где этого быть не может.
Каждая проверка делит пополам остаток: 100, 50, 25, 13, 7, 4, 2, 1. Это 7 проверок.
Индекс середины mid = (low + high) // 2. // делит и отбрасывает остаток: 14 // 2 это 7, и 15 // 2 тоже 7.
% даёт этот остаток: 15 % 2 это 1. Смотри, как работают оба.
Поиск это ты. Двигай заборы.
Жёлтая карточка это mid. Перетаскивай low или high на нужную карточку, пока не найдёшь 70.
Один шаг двоичного поиска в коде.
Пройди по шагам. Смотри, какой забор двигается.
Видео глючит в один момент из 64 минут.
Каждая проверка включает середину и спрашивает: глюк уже был? Сколько проверок нужно, чтобы сузить до 1 минуты?
Сколько догадок всегда хватит для числа от 1 до 1000?
low = 0, high = 15. Какую карточку поиск проверит первой?
Нажми на неё.
Как далеко заходит деление пополам?
Растяни размер списка до миллиарда.
Предыдущий урок: Сортировка по одному обмену · Следующий урок: Функции: дай рецепту имя · Часть курса: Как думает программист
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
