Бинарный поиск

От перебора к короткому примеру

Линейный поиск проверяет до n элементов. В отсортированном массиве сравнение середины с target позволяет сразу отбросить часть значений. Покажем lower bound: первый индекс, где a[i] ≥ target; если такого элемента нет, результат n.

Инвариант

Все индексы < left содержат значения < target; все индексы ≥ right содержат значения ≥ target. Не классифицированы элементы [left, right), а искомая позиция остаётся в [left, right], включая n. При left = right граница найдена.

1. a = [1, 3, 3, 8], target = 3. left = 0, right = 4; mid = 2, a[mid] = 3: сохраняем середину кандидатом, right = 2.
2. mid = 1, a[mid] = 3: right = 1. Затем mid = 0, a[mid] = 1: left = 1.
3. left = right = 1: получили первое вхождение 3. Для точного поиска нужно проверить i < n и a[i] == target.

Код на C++ и Python

Обе версии реализуют один контракт. Выберите язык кнопками над кодом; примеры проверяются на маленьких входах и граничных случаях.

#include <vector>

int first_not_less(const std::vector<int>& a, int target) {
    int left = 0;
    int right = static_cast<int>(a.size());
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

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

Проверьте контракт

• [] и target = 3 → 0
• [1, 3, 3, 8] и target = 3 → 1
• [1, 3, 3, 8] и target = 4 → 3
• [1, 3, 3, 8] и target = 9 → 4

Сложность и ограничения метода

• Пустой массив возвращает 0; если target больше всех элементов, возвращается n. Не читать a[n]. Повторы не мешают lower bound находить первый подходящий индекс.
• Каждый шаг сокращает неклассифицированный диапазон примерно вдвое: O(log n) времени при O(1) доступе к середине и сравнении; дополнительная память O(1). Сортировка исходного массива — отдельная работа, обычно O(n log n). Для одного запроса линейный поиск может быть выгоднее.
• C++: предполагаем, что размер массива помещается в int. Python: list поддерживает доступ по индексу; стоимость операций над большими целыми зависит от разрядности.
• Готовые функции: std::lower_bound в C++ и bisect_left в Python. Вставка в середину массива после поиска всё равно требует O(n) перемещений. Бинарное дерево поиска — другая структура данных.

Следующий шаг

• Полный урок: точный поиск и инвариант
• Границы, lower bound и повторы
• Бинарный поиск по ответу
• Задачи и самостоятельная практика