Бинарный поиск: От поиска позиции вставки до поиска по ответу

Все модификации двоичного поиска: lower_bound, upper_bound, проверка равенства, вещественный бинпоиск и метод поиска по ответу за O(log N).

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Бинарный поиск: предварительные знания, план уроков и практика →

Границы применимости двоичного поиска

Двоичный поиск применим к любой функции или предикату $P(x)$ , обладающему свойством монотонности:

\forall x \le y \implies P(x) \le P(y)

Это позволяет на каждом шаге отсекать ровно половину пространства поиска, обеспечивая сложность

O(\log N)

Ключевые реализации

cpp

// lower_bound: первый элемент >= target
int lowerBound(const vector<int>& arr, int target) {
    int l = 0, r = arr.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (arr[m] >= target) r = m;
        else l = m + 1;
    }
    return l;
}

// upper_bound: первый элемент > target
int upperBound(const vector<int>& arr, int target) {
    int l = 0, r = arr.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (arr[m] > target) r = m;
        else l = m + 1;
    }
    return l;
}

Что дальше?

Закрепите материал задачей: Повторить число.

Изучено — к практике →

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».