Что такое бинарный поиск? В каком условии он применим?

Идея бинарного поиска

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

Главное условие

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

Итеративная реализация

def binary_search(items: list[int], target: int) -> int:
    left = 0
    right = len(items) - 1

    while left <= right:
        middle = (left + right) // 2
        current = items[middle]

        if current == target:
            return middle
        if current < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Пример

numbers = [3, 7, 12, 18, 24, 31, 42]
print(binary_search(numbers, 24))
# 4

Сложность

Каждый шаг уменьшает диапазон поиска примерно в два раза, поэтому временная сложность равна O(log n). Итеративная реализация использует O(1) дополнительной памяти.

Важный нюанс

Бинарный поиск эффективен при быстром доступе к середине диапазона, например в массиве. В связном списке поиск середины сам требует прохода по элементам, поэтому преимущество алгоритма теряется.

Как ответить на собеседовании

Бинарный поиск находит элемент в отсортированном массиве, каждый раз сравнивая цель со средним элементом и отбрасывая половину диапазона. Его сложность — O(log n). Главный prerequisite — данные должны быть отсортированы, а доступ к середине должен быть эффективным.