A step-by-step look at binary search (part 08fd)

Разложим решение на шаги и объясним, что происходит на каждом из них.

Задача

Дан отсортированный список чисел arr и число target. Найти его индекс или вернуть -1, если элемента нет.

Решение

def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


print(binary_search([1, 3, 5, 7, 9, 11], 7))

Как это работает

На каждом шаге диапазон поиска сокращается вдвое: если середина меньше цели — ищем справа, иначе слева. Отсюда и логарифмическая скорость.

Пример работы

3

Сложность

O(log n) по времени, O(1) по памяти.

Разбор по шагам

1. Шаг 1. Входные данные. Проверяем, что приходит в функцию, и какие значения считаются корректными.
2. Шаг 2. Основной цикл. Именно здесь происходит вся работа; следим за изменениями переменных на каждой итерации.
3. Шаг 3. Результат. Убеждаемся, что возвращаемое значение соответствует условию задачи, включая крайние случаи.

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

Читайте также:

включая · Найти · условию · while · вернуть · Входные · данные · python · скорость · O(log · каждом · середина · логарифмическая · функцию · Читая · работает · сокращается · диапазон · соответствует · Задача · Пример · приходит · переменных · иначе · поиска · Результат · возвращаемое · индекс · Именно · Сложность