Расскажи про алгоритм двоичного поиска

Двоичный поиск — это эффективный алгоритм поиска элемента в отсортированном массиве. Он работает за O(log n), так как на каждом шаге делит диапазон поиска пополам.

Алгоритм:

1. Определяем границы (начало и конец массива).
2. Находим середину текущего диапазона.
3. Сравниваем элемент в середине с искомым:
   • Если равен — возвращаем индекс.
   • Если меньше — смещаем левую границу.
   • Если больше — смещаем правую границу.
4. Повторяем, пока границы не сойдутся.

Пример на Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Элемент не найден

Особенности:

• Работает только с отсортированными данными.
• Эффективнее линейного поиска (O(n) vs O(log n)).
• Подходит для больших массивов.
• Может быть реализован рекурсивно (но итеративный вариант предпочтительнее из-за отсутствия накладных расходов на вызовы).