Как работает алгоритм бинарного поиска?

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

1. Инициализация: Определяется левая и правая граница интервала поиска (обычно начало и конец массива).
2. Сравнение: Вычисляется индекс середины интервала. Значение по этому индексу сравнивается с искомым элементом.
3. Уменьшение интервала:
   • Если значение в середине совпадает с искомым, элемент найден.
   • Если значение в середине больше искомого, поиск продолжается в левой половине интервала. Правая граница сдвигается к середине-1.
   • Если значение в середине меньше искомого, поиск продолжается в правой половине интервала. Левая граница сдвигается к середине+1.
4. Повторение: Шаги 2 и 3 повторяются до тех пор, пока элемент не будет найден или интервал поиска не станет пустым.

Сложность алгоритма O(log n), что значительно эффективнее линейного поиска для больших массивов.

Пример реализации на Python:

def binary_search(arr, target):
    """
    Реализация бинарного поиска.
    Принимает отсортированный массив и искомое значение.
    Возвращает индекс элемента или -1, если элемент не найден.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Вычисляем индекс середины
        mid_val = arr[mid]      # Получаем значение в середине

        if mid_val == target:
            return mid  # Элемент найден
        elif mid_val < target:
            left = mid + 1  # Искомое значение больше, ищем в правой части
        else: # mid_val > target
            right = mid - 1 # Искомое значение меньше, ищем в левой части

    return -1 # Элемент не найден