Объясните принцип работы алгоритма бинарного поиска и его основные характеристики.

Бинарный поиск — это алгоритм поиска элемента в отсортированном массиве или списке.

Принцип работы:

• Сначала выбирается средний элемент массива.
• Если искомый элемент равен среднему, поиск завершается успешно.
• Если искомый элемент меньше среднего, поиск продолжается в левой (меньшей) половине массива.
• Если больше — в правой (большей) половине.
• Процесс повторяется рекурсивно или итеративно, пока элемент не будет найден или не останется подмассив для поиска.

Основные характеристики:

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

Пример на 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  # элемент не найден

# Использование
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7))  # Выведет индекс 3