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

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

Главное условие

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

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

Алгоритм итеративно делит массив пополам, сужая область поиска:

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

Пример на Python

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

    while left <= right:
        mid = (left + right) // 2
        mid_val = sorted_array[mid]

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

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

# Пример использования
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23)) # Вывод: 5
print(binary_search(arr, 1))  # Вывод: -1

В стандартной библиотеке Python для этих целей существует модуль bisect.