Какой алгоритм работы двоичного поиска

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

1. Определяем границы поиска — левую (low) и правую (high).
2. Находим средний элемент (mid = (low + high) // 2).
3. Сравниваем искомый элемент (target) с mid:
   • Если target == mid → элемент найден.
   • Если target < mid → ищем в левой половине (high = mid - 1).
   • Если target > mid → ищем в правой половине (low = mid + 1).
4. Повторяем, пока low <= high. Если границы пересеклись — элемента нет.

Пример на Python:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # Элемент не найден

Нюансы:

• Массив должен быть отсортирован.
• Для больших массивов mid = low + (high - low) // 2 избегает переполнения.