В чем заключается суть двоичного поиска и в каких случаях его применяют?

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

Применяют двоичный поиск, когда данные отсортированы и нужно быстро найти элемент или определить его отсутствие. Например, поиск слова в словаре, поиск значения в отсортированном массиве чисел.

Пример на Python:

from bisect import bisect_left

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, 5))  # Выведет 2