Первая и последняя подходящая позиция

Для [1,2,2,4] и порога 2 предикат a[i] >= 2 даёт false,true,true,true; бинарный поиск должен вернуть границу перехода — индекс 1.

Как найти первую позицию со значением не меньше target?

Найти первый индекс, где значение отсортированного массива не меньше target; при отсутствии вернуть n.

Сканирование до первого подходящего элемента

Сканировать слева до первого подходящего элемента за O(n).

Почему повторные запросы требуют использовать порядок?

При множестве запросов повторный линейный проход игнорирует монотонность условия.

Ищем переход false → true, а не совпадение

Предикат values[i] >= target сначала ложен, а затем истинен; нужно найти место его единственного перехода.

Что доказано слева от lo и справа от hi?

Обозначим искомую границу через p. Граница p всегда находится в закрытом диапазоне кандидатов [lo, hi]: значение hi = n допустимо, когда подходящей позиции нет. При этом непроверенные позиции массива образуют полуинтервал [lo, hi); позиции строго левее lo доказанно ложны, а позиции от hi доказанно истинны, если hi < n.

Сужаем полуинтервал [lo, hi)

Начать lo=0, hi=n. Пока lo<hi: если mid подходит, присвоить hi=mid, иначе lo=mid+1. Вернуть lo.

Нижняя граница на C++17 и Python 3

C++17

#include <cassert>
#include <vector>
using namespace std;

int lowerBoundary(const vector<int>& values, int target) {
    int lo = 0;
    int hi = static_cast<int>(values.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (values[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    assert(lowerBoundary({1, 2, 2, 4}, 2) == 1);
    assert(lowerBoundary({1, 2, 2, 4}, 5) == 4);
    assert(lowerBoundary({}, 5) == 0);
}

Python 3

def lower_boundary(values: list[int], target: int) -> int:
    lo = 0
    hi = len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo


assert lower_boundary([1, 2, 2, 4], 2) == 1
assert lower_boundary([1, 2, 2, 4], 5) == 4
assert lower_boundary([], 5) == 0

Логарифмический поиск позиции вставки

O(log n) времени и O(1) памяти. Для upper bound заменить условие на values[mid] > target.

Пустой массив, дубликаты и граница n

Пустой массив; все элементы меньше target — n; все не меньше — 0; дубликаты; target между значениями.

Тесты на начало, середину и конец диапазона

[],3 -> 0, [1,2,2,4],2 -> 1, target 0 -> 0, target 5 -> 4, target 3 -> 3.

Сигналы «первый подходящий» и «последний неподходящий»

Нужна первая/последняя позиция, количество вхождений или граница монотонного свойства.

Когда предикат не образует единственного перехода?

Нельзя смешивать закрытый [lo,hi] и полуоткрытый [lo,hi) шаблоны без повторного доказательства.

Мини-проверка: почему подходящий mid нельзя сразу вернуть?

Вопрос: почему подходящий mid не возвращается сразу? Ответ: слева может находиться более ранняя подходящая позиция.

Мини-проверка: что означает результат n?

Вопрос: что означает результат n? Ответ: подходящего элемента нет, но n является корректной позицией вставки.

Найдите границу в булевой последовательности

Для [1,2,2,2,5] найдите lower и upper boundary числа 2 и вычислите количество вхождений разностью.

Реализуйте верхнюю границу без подсказки

Задача 1

Реализуйте upper boundary и с его помощью посчитайте число элементов, строго не превосходящих target.

Граница — это поиск монотонного предиката

Граничный бинарный поиск сохраняет кандидата и продолжает искать более ранний переход предиката.