Двоичный поиск

Представьте игру «Угадай число». Друг загадал число от 1 до 100 и на каждую попытку отвечает «больше» или «меньше». Можно называть числа подряд: 1, 2, 3… Тогда попыток может понадобиться сто. А можно сразу назвать 50: после любого ответа половина чисел отпадает.

Со списком происходит то же самое. Чтобы найти в нём число, функция может сравнить с ним каждый элемент по очереди. Такой перебор называют линейным поиском. В списке из миллиона элементов ему может понадобиться миллион сравнений:

def linear_search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1


nums = [3, 8, 15, 21, 30, 42, 57]
print(linear_search(nums, 42))  # 5
print(linear_search(nums, 10))  # -1

Давайте разберём, что делает функция:

1. enumerate(nums) выдаёт пары из индекса и элемента.
2. Как только элемент равен цели, функция возвращает его индекс. Для 42 это 5.
3. Если цикл прошёл весь список без совпадений, функция возвращает -1. Так вышло с 10.

Деление пополам

Список nums отсортирован по возрастанию, и это позволяет искать быстрее. Двоичный поиск сравнивает цель со средним элементом, как игрок называет середину. Если средний меньше цели, то и все элементы левее него меньше цели, и левую половину можно отбросить. Если больше — отбрасывается правая половина.

Поиск хранит две границы и средний индекс:

• lo — индекс первого элемента, где цель ещё может быть;
• hi — индекс последнего такого элемента;
• mid — средний индекс, (lo + hi) // 2.

Так идёт поиск числа 10 в том же списке:

Проверенный средний элемент в новые границы не входит. Когда lo стал больше hi, искать негде, и ответ — «не найдено». Если средний элемент равен цели, поиск сразу возвращает его индекс.

Здесь аналогия с игрой заканчивается. Друг отвечает «больше» или «меньше» честно, а список отвечает своим порядком. Если список не отсортирован, его ответы обманывают, и поиск отбрасывает не ту половину.

Поиск в программе

Вот тот же поиск в коде — для числа 30, которое в списке есть. Нажимайте «Следующий шаг» и следите за lo, hi и mid: после каждого сравнения одна из границ перескакивает через mid.

Цикл while lo <= hi идёт, пока между границами остаётся хотя бы один элемент. На третьем сравнении lo и hi оба равны 4, и средний элемент — как раз 30. Если бы 30 в списке не было, hi стал бы меньше lo. Цикл бы закончился, а в found осталось бы -1.

Сколько нужно шагов

Каждый шаг вдвое сокращает часть списка, где осталась цель. Миллион элементов делится пополам около 20 раз, пока не останется один, поэтому двоичному поиску хватает около 20 сравнений.

Этот вопрос часто задают на собеседовании: «Как работает двоичный поиск и что ему нужно?» Хороший ответ состоит из двух частей:

• поиск сравнивает цель со средним элементом и отбрасывает половину, поэтому миллиону элементов хватает около 20 шагов;
• список должен быть отсортирован, иначе цель может оказаться в отброшенной половине.

Модуль bisect

В стандартной библиотеке двоичный поиск уже написан. Функция bisect.bisect_left(nums, x) возвращает позицию, куда x можно вставить, не нарушив порядок. Если x есть в списке, это индекс его первого вхождения:

import bisect

nums = [3, 8, 15, 21, 30, 42, 57]
i = bisect.bisect_left(nums, 42)
print(i, nums[i])  # 5 42
j = bisect.bisect_left(nums, 10)
print(j, j < len(nums) and nums[j] == 10)  # 2 False

Для 10 функция вернула 2 — место между 8 и 15, а не признак «не найдено». Поэтому найденный индекс нужно проверить:

1. Индекс меньше длины списка. Для цели больше всех элементов функция вернёт len(nums), и без этой проверки nums[j] дал бы IndexError.
2. Элемент на этом индексе равен цели.

Частая ошибка

Двоичный поиск запускают на неотсортированном списке:

import bisect

nums = [7, 1, 5, 3]
i = bisect.bisect_left(nums, 1)
print(i, nums[i] == 1)  # 0 False

Ошибки нет, но ответ неверный: число 1 в списке есть, а проверка говорит, что его нет. Поиск рассчитывает, что левее каждого элемента стоят только меньшие числа, а здесь 7 стоит раньше 1. Отсортируйте список перед поиском — nums.sort() или sorted(nums).

Главное

• Линейный поиск проверяет элементы по очереди: на миллион элементов — до миллиона сравнений.
• Двоичный поиск сравнивает цель со средним элементом и отбрасывает половину, поэтому ему хватает около 20 сравнений.
• Границы lo и hi сходятся; когда lo больше hi, цели в списке нет.
• Поиск работает только на отсортированном списке, а индекс от bisect_left нужно проверить.