Справочник · модуль 17 «Финал»

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

Бинарный поиск работает в отсортированном списке. Смотрим на середину и выбрасываем половину, где нужного числа точно нет. Так список сжимается вдвое на каждом шаге.

Пример

numbers = [3, 8, 15, 21, 34, 42, 57, 63]
target = 42
low = 0
high = len(numbers) - 1
while low <= high:
    mid = (low + high) // 2
    if numbers[mid] == target:
        print("нашли на месте", mid)
        break
    if numbers[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

нашли на месте 5

Учитель в уроке А это бинарный поиск. Список должен быть отсортирован. Смотрим на середину. Если нужное число больше, левая половина нам не нужна, и мы её выбрасываем. И так по кругу. Для сорока двух хватило двух шагов вместо шести.

Запомнить

Бинарный поиск — как игра «угадай число». Каждый раз спрашиваешь, больше или меньше, и отбрасываешь половину.

Тема из урока 17.1 «Поиск» курса PythonAZ.

В этом же уроке

• Алгоритм
• Перебор
• Сколько шагов (O)