← Все уроки

Урок 12.2

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

▶ Теория

Если список отсортирован, искать можно вдвое быстрее: смотреть в середину и выкидывать половину.

def binary_search(numbers, target):
    left, right = 0, len(numbers) - 1

    while left <= right:
        mid = (left + right) // 2
        if numbers[mid] == target:
            return mid
        elif numbers[mid] < target:
            left = ...            # правая половина
        else:
            right = ...           # левая половина

    return -1

Проверка даёт отсортированный список numbers и число target. Напишите binary_search и напечатайте индекс найденного или -1.

Подсказка

Держите две границы куска, где ещё может быть ответ, и сужайте его вдвое.

Середина — (left + right) // 2: целое деление, индекс не бывает дробным. Сдвигать границы нужно на mid + 1 и mid - 1, иначе цикл зациклится. Цикл идёт, пока left <= right.