二分查找，从区间不变量开始

Binary search 的难点往往不在“每次排除一半”，而在边界。区间是否包含右端点，更新后还剩下哪些候选位置，循环结束时返回什么，这三个问题需要使用同一套约定。

这篇笔记只解决一个问题：在有序数组中，找到第一个不小于目标值的位置。

先把问题说清楚

给定一个非递减数组 a 和目标值 target，返回最小的下标 p，使得 a[p] >= target。如果不存在这样的位置，就返回数组长度 n。

例如，对数组 [1, 3, 3, 5, 8]：

这个位置也是标准库 std::lower_bound 所表示的边界。先定义返回值，再写循环，比写完代码后猜它返回什么更可靠。

维护一个左闭右开的区间

使用 [left, right) 表示尚未排除的元素范围，初始值为 [0, n)。在每次循环开始时，保持两个条件：

1. left 左侧的元素都小于 target。
2. 从 right 开始的元素都不小于 target。

这里不要求 right 指向一个可以访问的元素。它可以等于 n，表示右侧暂时没有元素。

区间不变量描述的是“哪些位置已经确定”，而不是要求某个变量始终指向答案。

中点落在目标值左侧

如果 a[mid] < target，由于数组有序，mid 及其左侧尚未排除的元素都可以舍弃。令 left = mid + 1。

中点可能就是边界

如果 a[mid] >= target，mid 仍可能是答案，但第一个满足条件的位置也可能更靠左。令 right = mid，继续检查左侧。

注意这里没有写成 mid - 1。右端点是不包含在区间内的边界，不能把另一套闭区间写法的更新规则直接搬过来。

把约定翻译成代码

#include <cstddef>
#include <vector>

std::size_t first_not_less(const std::vector<int>& a, int target) {
    std::size_t left = 0;
    std::size_t right = a.size();

    while (left < right) {
        const auto mid = left + (right - left) / 2;

        if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

循环条件为 left < right。只要区间中还有元素，就可以访问中点；两端相遇时，所有元素都已经被归到边界的某一侧。

中点写成 left + (right - left) / 2，可以避免先计算 left + right 时可能出现的整数溢出。两条分支都会让区间长度严格减小，因此循环不会停在同一个状态。

每轮排除约一半的候选元素，只维护固定数量的变量：

$$ T(n) = O(\log(n + 1)), \qquad S(n) = O(1). $$

这里把时间复杂度写成 $O(\log(n + 1))$，也包含空数组这一种输入。

用边界输入检查自己

先看空数组，再看单个元素，最后检查重复值和两端之外的目标。它们比随手挑几个普通输入更容易暴露错误。

#include <cassert>

void check_boundaries() {
    assert(first_not_less({}, 3) == 0);
    assert(first_not_less({3}, 2) == 0);
    assert(first_not_less({3}, 3) == 0);
    assert(first_not_less({3}, 4) == 1);

    const std::vector<int> a{1, 3, 3, 5, 8};
    assert(first_not_less(a, 0) == 0);
    assert(first_not_less(a, 3) == 1);
    assert(first_not_less(a, 4) == 3);
    assert(first_not_less(a, 9) == a.size());
}

如果接下来要判断目标值是否存在，还需要检查返回位置是否小于 a.size()，然后才能读取 a[p]。找到插入位置，不等于找到了目标元素。

留给下一次复习的问题

• 为什么 a[mid] == target 时仍要继续向左找？
• 如果要找第一个严格大于目标值的位置，哪个比较条件需要改变？
• 能否把数组上的查找，改写为寻找一个单调判断条件的分界点？

复习时先回答这些问题，再默写代码。边界约定能够解释每一行更新，模板才算真正属于自己。