Алгоритмы поиска

Мурад загадывает число от 1 до 100, а Айсель должна его угадать. После каждой попытки Мурад говорит только «больше», «меньше» или «угадала». Если Айсель будет называть числа подряд — 1, 2, 3…, — ей может понадобиться 100 попыток. Но если начать с 50 и каждый раз делить промежуток пополам, хватит не более 7 попыток. Эти два подхода — два знаменитых алгоритма: линейный и двоичный поиск.

Линейный поиск

При линейном (последовательном) поиске элементы списка по очереди, начиная с первого, сравниваются с искомым значением. Когда нужный элемент найден, поиск останавливается; если мы дошли до конца списка и не нашли его, значит, такого элемента нет.

Преимущество линейного поиска — простота: он работает с любым списком, даже неупорядоченным. Недостаток — медлительность: в худшем случае для списка из n элементов нужно n сравнений.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

numbers = [7, 3, 23, 9, 15]
print(linear_search(numbers, 23))
print(linear_search(numbers, 4))

2
-1

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

Двоичный (бинарный) поиск работает только с упорядоченным списком (например, отсортированным по возрастанию), зато очень быстро. На каждом шаге искомое значение сравнивается со средним элементом промежутка, и сразу половина списка отбрасывается.

1. 1
   Найди середину

   Возьми элемент в середине текущего промежутка поиска.

2. 2
   Сравни

   Если средний элемент равен искомому, элемент найден и поиск окончен.

3. 3
   Отбрось половину

   Если искомое меньше среднего элемента, продолжай поиск в левой половине, если больше — в правой.

4. 4
   Повтори

   Повторяй шаги 1–3, пока элемент не найдётся или промежуток не станет пустым. Пустой промежуток означает, что элемента в списке нет.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

numbers = [3, 8, 12, 17, 23, 31, 37, 42, 50]
print(binary_search(numbers, 37))
print(binary_search(numbers, 5))

(6, 2)
(-1, 3)

Что быстрее?

При двоичном поиске каждое сравнение уменьшает список вдвое, поэтому при удвоении списка добавляется всего одно сравнение. На больших списках разница поразительна: