Binary Search: Основы

Бинарный поиск — не только для отсортированных массивов. Мощная техника для поиска ответа в пространстве решений с логарифмической сложностью O(log n)

#1. Суть паттерна

Binary Search — алгоритм поиска, делящий диапазон поиска пополам на каждом шаге. Применяется не только к массивам, но и к пространству возможных ответов.

#1.1 Термины

Монотонная функция — функция, которая только возрастает или только убывает.

Бинарный поиск — поиск делением диапазона пополам за O(log n).

#Когда применять

✅ Отсортированный массив — поиск элемента, границ, позиции вставки
✅ Монотонная функция — можно определить, больше или меньше цели
✅ Binary Search on Answer — поиск минимального/максимального возможного значения
✅ Поиск пика — элемент больше соседей

#Предусловия

Монотонность — функция должна быть возрастающей или убывающей
Границы — известны нижняя и верхняя границы поиска
Проверка — можно проверить, выполняется ли условие за O(1) или O(n)

#2. Базовый шаблон

#Поиск элемента в отсортированном массиве

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  # Не найдено

#Поиск левой границы (первый элемент ≥ target)

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

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] >= target:
            result = mid
            right = mid - 1  # Продолжаем поиск слева
        else:
            left = mid + 1

    return result

#Поиск правой границы (последний элемент ≤ target)

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

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            result = mid
            left = mid + 1  # Продолжаем поиск справа
        else:
            right = mid - 1

    return result

#3. Разбор задач

#Задача 1: Binary Search (LeetCode 704) 🟩 Easy

Ссылка: https://leetcode.com/problems/binary-search/

Условие: Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target. Напишите функцию для поиска target в nums.

Если target существует в массиве, верните его индекс. В противном случае верните -1.

Примеры:

Ввод: nums = [-1, 0, 3, 5, 9, 12], target = 9
Вывод: 4

Ввод: nums = [-1, 0, 3, 5, 9, 12], target = 2
Вывод: -1

Ограничения:

1 <= nums.length <= 10⁴
-10⁴ < nums[i], target < 10⁴
Все целые числа в nums уникальны
nums отсортирован по возрастанию

Решение:

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Объяснение:

Классический бинарный поиск
mid = left + (right - left) // 2 защищает от переполнения
Условие left <= right позволяет найти элемент в окне размера 1

Сложность:

Время: O(log n)
Память: O(1)

#Задача 2: Search Insert Position (LeetCode 35) 🟩 Easy

Ссылка: https://leetcode.com/problems/search-insert-position/

Условие: Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target. Найдите target в массиве и верните его индекс.

Если target не найден, верните индекс, куда он должен быть вставлен для сохранения порядка сортировки.

Примеры:

Ввод: nums = [1, 3, 5, 6], target = 5
Вывод: 2

Ввод: nums = [1, 3, 5, 6], target = 2
Вывод: 1

Ввод: nums = [1, 3, 5, 6], target = 7
Вывод: 4

Ограничения:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums содержит уникальные значения
nums отсортирован по возрастанию

Решение:

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left  # Позиция вставки

Объяснение:

Если не нашли target, left указывает на позицию вставки
После цикла left — первый элемент > target (или len(nums))

Сложность:

Время: O(log n)
Память: O(1)

#Задача 3: Find First and Last Position (LeetCode 34) 🟩 Medium

Ссылка: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Условие: Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target.

Найдите начальную и конечную позицию target в массиве.

Примеры:

Ввод: nums = [5, 7, 7, 8, 8, 10], target = 8
Вывод: [3, 4]

Ввод: nums = [5, 7, 7, 8, 8, 10], target = 6
Вывод: [-1, -1]

Решение:

def searchRange(nums, target):
    def find_left():
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        return result

    def find_right():
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        return result

    return [find_left(), find_right()]

Объяснение:

Два отдельных бинарных поиска
find_left: ищем первый элемент ≥ target
find_right: ищем последний элемент ≤ target

Сложность:

Время: O(log n)
Память: O(1)

#4. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильное условие цикла

Проблема: left < right vs left <= right.

# ❌ Неправильно для поиска элемента — может пропустить последний
while left < right:
    ...

# ✅ Правильно для поиска элемента
while left <= right:  # Позволяет найти элемент в окне размера 1
    ...

Почему это неправильно: При left < right цикл завершится, когда окно размера 1, и элемент может быть пропущен.

#❌ Ошибка 2: Переполнение при вычислении mid

Проблема: (left + right) // 2 может переполниться.

# ❌ Неправильно — может переполниться
mid = (left + right) // 2

# ✅ Правильно — защита от переполнения
mid = left + (right - left) // 2

#5. Шпаргалка

Задача	Ключевая идея
Binary Search	Классический поиск, left <= right
Search Insert	left указывает позицию вставки
Find First/Last	Два отдельных поиска

#6. Заключение

Binary Search: Основы — базовый паттерн для поиска в отсортированных массивах.

Ключевые принципы:

left <= right для поиска элемента
mid = left + (right - left) // 2 — защита от переполнения
Для границ: отдельные функции для left и right

Задача

Ключевая идея

Binary Search

Классический поиск, left <= right

Search Insert

left указывает позицию вставки

Find First/Last

Два отдельных поиска