Что такое двоичный поиск?

Двоичный поиск (Binary Search)

Двоичный поиск - это эффективный алгоритм поиска элемента в отсортированном массиве за O(log n) времени путем постоянного деления диапазона поиска пополам.

Основной принцип

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

def binary_search(arr, target):
    """
    Поиск элемента в отсортированном массиве
    Возвращает индекс элемента или -1, если не найден
    Временная сложность: O(log n)
    Пространственная сложность: O(1)
    """
    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 = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]
print(binary_search(arr, 23))  # Вывод: 5
print(binary_search(arr, 10))  # Вывод: -1

Пошаговый пример

Поиск числа 23 в массиве [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]:

Шаг 1: left=0, right=10, mid=5
  arr[5]=23 == 23 ✓ Найдено! Возвращаем 5

Если бы искали 10:

Шаг 1: left=0, right=10, mid=5 → arr[5]=23
  23 > 10, поэтому right=4 (ищем слева)
  
Шаг 2: left=0, right=4, mid=2 → arr[2]=8
  8 < 10, поэтому left=3 (ищем справа)
  
Шаг 3: left=3, right=4, mid=3 → arr[3]=12
  12 > 10, поэтому right=2 (ищем слева)
  
Шаг 4: left=3, right=2
  left > right, выходим из цикла → Не найдено!

Рекурсивная реализация

def binary_search_recursive(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1  # Не найдено
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Практические вариации

1. Поиск первого вхождения (левая граница)

def find_first(arr, target):
    """Найти первый индекс элемента"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Ищем дальше слева
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

arr = [1, 2, 2, 2, 3, 4]
print(find_first(arr, 2))  # 1 (первое вхождение)

2. Поиск последнего вхождения (правая граница)

def find_last(arr, target):
    """Найти последний индекс элемента"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Ищем дальше справа
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

arr = [1, 2, 2, 2, 3, 4]
print(find_last(arr, 2))  # 3 (последнее вхождение)

3. Поиск по условию (например, первого элемента >= target)

def find_first_gte(arr, target):
    """Найти первый элемент >= target"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left if left < len(arr) else -1

arr = [1, 3, 5, 7, 9]
print(find_first_gte(arr, 4))  # 2 (индекс элемента 5)

Использование встроенных функций Python

import bisect

arr = [1, 3, 5, 7, 9, 11]

# bisect_left - позиция вставки слева (первое вхождение)
pos = bisect.bisect_left(arr, 5)  # 2

# bisect_right - позиция вставки справа (последнее вхождение)
pos = bisect.bisect_right(arr, 5)  # 3

# Вставить элемент на правильное место
bisect.insort(arr, 6)  # arr = [1, 3, 5, 6, 7, 9, 11]

Сложность анализ

Для массива из 1 млн элементов:

• Линейный поиск: до 1 млн сравнений
• Двоичный поиск: максимум 20 сравнений

Когда использовать

1. Отсортированные данные - основное условие
2. Частые поиски - хороша амортизация
3. Большие наборы данных - экспоненциальная разница
4. Read-only структуры - сортировка один раз

Когда НЕ использовать

1. Часто меняются данные - стоимость поддержки сортировки
2. Связные списки - нет прямого доступа к середине
3. Очень маленькие массивы - overhead больше пользы
4. Потоковые данные - нельзя отсортировать заранее