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

Алгоритм бинарного поиска — это эффективный метод нахождения позиции целевого элемента в отсортированном массиве (или списке).

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

1. Начало поиска: Определение границ интервала поиска - начало (left) и конец (right) массива.
2. Вычисление середины: На каждой итерации определяется средний индекс (middle) текущего интервала: middle = (left + right) / 2.
3. Сравнение: Целевой элемент сравнивается с элементом по индексу middle.
   • Если целевой элемент равен элементу по индексу middle, поиск завершен, элемент найден.
   • Если целевой элемент меньше элемента по индексу middle, поиск сужается до левой половины интервала: right = middle - 1.
   • Если целевой элемент больше элемента по индексу middle, поиск сужается до правой половины интервала: left = middle + 1.
4. Повторение: Шаги 2 и 3 повторяются до тех пор, пока целевой элемент не будет найден или пока интервал поиска не станет пустым (left > right).
5. Результат: Если элемент найден, возвращается его индекс. Если нет, возвращается индикатор отсутствия (например, -1).

Преимущества:

• Высокая скорость (логарифмическая сложность 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 # Элемент не найден