Каков принцип работы алгоритма бинарного поиска?

Бинарный поиск (binary search) — это эффективный алгоритм для нахождения элемента в отсортированном массиве. Его принцип основан на стратегии "разделяй и властвуй": на каждом шаге алгоритм отбрасывает половину массива, в которой искомого элемента точно нет.

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

Алгоритм

1. Определить левую (left) и правую (right) границы поиска (изначально — весь массив).
2. Пока left <= right, вычислить центральный индекс mid.
3. Сравнить искомый элемент (target) с элементом arr[mid]:
   • Если они равны, элемент найден, вернуть mid.
   • Если target больше arr[mid], продолжить поиск в правой половине, сместив left на mid + 1.
   • Если target меньше arr[mid], продолжить поиск в левой половине, сместив right на mid - 1.
4. Если границы поиска сошлись (left > right), элемент в массиве отсутствует.

Пример на Python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        # Вычисляем середину, избегая возможного переполнения для больших чисел
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid  # Элемент найден
        elif arr[mid] < target:
            left = mid + 1  # Искать в правой половине
        else:
            right = mid - 1  # Искать в левой половине

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

Ключевые моменты

• Главное требование: Массив должен быть отсортирован.
• Эффективность: Значительно превосходит линейный поиск на больших объемах данных.
• Реализация: Может быть как итеративной (цикл while), так и рекурсивной.