TwiddleLab / Код / Алгоритмы в движении

Линейный и двоичный поиск, ещё раз

Урок 2 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Линейный поиск проверяет элементы по одному: до n проверок.
• Двоичный поиск проверяет середину и отбрасывает половину. Ему нужно около log₂ n проверок: 20 на миллион.
• Если удвоить данные, двоичному поиску нужна всего одна лишняя проверка.
• Двоичный поиск работает только на отсортированных данных.

Начать урок

Как идёт урок

1. Найди одно имя пользователя среди миллиона. Есть короткий путь?

   Имена стоят по алфавиту. Смотришь на имя посередине и отбрасываешь половину, где его быть не может, снова и снова. Поставь, на сколько имён придётся посмотреть.

2. Бегун проверяет по одному. Прыгун делит пополам.

   Та же полка, та же скорость: по одной проверке за такт у каждого. Запусти гонку.

3. Побудь прыгуном.

   63 книги, имена скрыты, по алфавиту. Найди имя за 6 проверок или меньше.

4. Два способа искать.

   Линейный поиск проверяет элементы по одному. На n элементах может понадобиться n проверок.

   Двоичный поиск проверяет середину и отбрасывает половину, где ответа быть не может. Ему нужно около log₂ n проверок: сколько раз n делится пополам до 1. Миллион: 20.

   Удвоение данных добавляет всего одну проверку. Такой медленный рост называется логарифмическим временем. Цена: данные должны быть отсортированы.

5. Увеличивай полку. Когда прыгуну понадобится 30 проверок?

   Каждая остановка удваивает число имён.

6. Собери свой двоичный поиск.

   Он печатает, где имя, или -1, если его нет. Три теста.

7. Поиск говорит, что kai здесь нет. А он есть.

   Запусти поиск, потом нажми на книгу, которая его ломает.

8. 1 048 576 отсортированных имён. Сколько раз это можно поделить пополам, пока не останется 1 имя?

   1 048 576 это 2, умноженное само на себя сколько-то раз. В математике это число называется log₂ 1 048 576.

   Каждое деление пополам делит на 2. Двадцать делений на 2 доводят 2²⁰ = 1 048 576 до 1.

9. Найди 63. Нажимай на книги в том порядке, в каком их проверяет двоичный поиск.

   low = 0, high = 14, mid = (low + high) // 2.

10. Теперь обыщи всех людей на Земле.

    Двигай от своего класса до всей планеты, отсортированной по именам.

Предыдущий урок: Считаем шаги · Следующий урок: Сортировка выбором · Часть курса: Алгоритмы в движении

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.