Binary Search

Поддерживается полуоткрытый диапазон [lo, hi), про который известно: если искомое значение есть в массиве, оно лежит внутри этого диапазона. Изначально диапазон — весь массив. На каждом шаге вычисляется mid = lo + (hi - lo) / 2, и сравнение a[mid] с x позволяет отбросить одну из половин, не нарушая инвариант. Цикл заканчивается, когда диапазон пуст (lo == hi) — к этому моменту либо элемент найден, либо доказано, что его нет.A half-open range [lo, hi) is maintained, about which one thing is known: if the target value is in the array, it lies inside this range. Initially the range is the whole array. At each step mid = lo + (hi - lo) / 2 is computed, and comparing a[mid] to x lets one half be discarded without breaking the invariant. The loop ends when the range is empty (lo == hi) — by then either the element has been found, or its absence has been proven.

lower_bound и upper_bound поддерживают тот же самый инвариант диапазона, но никогда не "находят и останавливаются" — они сужают диапазон до одной точки, которая и есть ответ: lower_bound ищет первый индекс, где a[i] ≥ x (сравнение a[mid] < x сдвигает lo), upper_bound — первый индекс, где a[i] > x (сравнение a[mid] <= x сдвигает lo). Разница ровно в одном символе внутри условия, но это и есть разница между "первое вхождение x" и "первый элемент строго после всех x".lower_bound and upper_bound maintain the exact same range invariant, but never "find and stop" — they narrow the range down to a single point that is itself the answer: lower_bound looks for the first index where a[i] ≥ x (the comparison a[mid] < x moves lo), upper_bound looks for the first index where a[i] > x (the comparison a[mid] <= x moves lo). The difference is exactly one symbol inside the condition, but that's the entire difference between "the first occurrence of x" and "the first element strictly after all the x's."

// классический поиск: найти индекс x или -1// classic search: find x's index or -1
int binary_search(const std::vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2; // не (lo+hi)/2 — не переполнится// not (lo+hi)/2 — won't overflow
        if (a[mid] == x) return mid;
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return -1;
}

// lower_bound: первый индекс, где a[i] >= x// lower_bound: first index where a[i] >= x
int lower_bound(const std::vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// upper_bound: первый индекс, где a[i] > x// upper_bound: first index where a[i] > x
int upper_bound(const std::vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Столбики — отсортированный массив со случайными (иногда повторяющимися) значениями. Синяя рамка — текущий диапазон [lo, hi), жёлтый столбик — mid. Переключатель режима меняет то, какое условие используется для сдвига границ: обычный поиск останавливается при совпадении, lower_bound и upper_bound всегда сужают диапазон до одной точки.The bars are a sorted array with random (sometimes repeating) values. The blue outline is the current range [lo, hi), the yellow bar is mid. The mode switch changes which condition shifts the boundaries: plain search stops on a match, lower_bound and upper_bound always narrow the range down to a single point.

Каждый шаг умножает размер диапазона на коэффициент ≤ 1/2 (при делении hi-lo пополам, целочисленно, хуже случай — округление вниз даёт (n-1)/2). Диапазон становится пустым, когда n · (1/2)^k < 1, то есть k > log₂ n — отсюда и граница O(log n): не "примерно", а как прямое следствие геометрической прогрессии с знаменателем 1/2.Each step multiplies the range size by a factor ≤ 1/2 (integer-dividing hi-lo, worst case rounding down gives (n-1)/2). The range becomes empty when n · (1/2)^k < 1, i.e. k > log₂ n — hence the O(log n) bound: not "roughly," but as a direct consequence of a geometric progression with ratio 1/2.

Условие для применимости — не просто "массив отсортирован", а то, что предикат "a[i] < x" (или любой предикат в условии сдвига) монотонен по i: как только он стал истинным, он остаётся истинным для всех следующих i. Это чуть более общее условие, чем числовая сортировка, и именно оно — то, что действительно нарушается в задачах вроде "поиск в почти отсортированном, но перемешанном локально массиве": там предикат не монотонен, и биение диапазона пополам может отбросить половину, где ответ есть.The applicability condition isn't just "the array is sorted," but that the predicate "a[i] < x" (or whatever predicate drives the boundary shift) is monotonic in i: once it becomes true, it stays true for every later i. This is a slightly more general condition than numeric sortedness, and it's exactly what breaks in problems like "search a nearly-sorted but locally shuffled array" — there the predicate isn't monotonic, and halving the range can discard the half that actually contains the answer.