Chapter 29: Binary Search Algorithms

二分查找算法解决的主问题，是在一个已经形成单调边界的区间里，把“线性扫描寻找目标”改写成“不断缩小候选区间”。本章围绕 std::binary_search、std::lower_bound、std::upper_bound、std::equal_range 和 std::partition_point 展开，目标是让读者能判断一个区间是否满足二分前提，能选择正确的边界算法，并能解释迭代器能力如何改变真实成本。

贯穿材料使用一个升序价格表。它的元素存在重复值，因此比“查找单个整数是否存在”更能暴露二分算法的边界含义：存在性、左边界、右边界、等价范围和插入点都能从同一份数据中读出来。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};
    int target = 101;

    bool exists = std::binary_search(prices.begin(), prices.end(), target);
    auto first = std::lower_bound(prices.begin(), prices.end(), target);
    auto last = std::upper_bound(prices.begin(), prices.end(), target);
    auto range = std::equal_range(prices.begin(), prices.end(), target);

    std::cout << std::boolalpha << exists << '\n';
    std::cout << (first - prices.begin()) << ' ' << (last - prices.begin()) << '\n';
    std::cout << (range.first - prices.begin()) << ' ' << (range.second - prices.begin()) << '\n';
}

这段代码的关键结果是 target == 101 的等价元素占据半开区间 [2, 5)。binary_search 只能回答是否存在；lower_bound 给出左边界；upper_bound 给出右边界后一个位置；equal_range 一次返回两个边界。C++ 标准草案在 [alg.binary.search] 中把这些算法描述为二分查找版本，并强调它们依赖区间相对比较表达式已经分区，同时在非随机访问迭代器上会产生线性步进成本；这些规则也可在 C++ draft binary search algorithms 和 cppreference binary search operations 中交叉核对。

本章的判断顺序是：先确认区间对当前比较表达式形成单调分区；再确认要的是存在性、左边界、右边界、等价范围还是谓词分界点；接着检查 comparator 的方向和等价定义；最后根据 iterator category 估算比较次数、步进次数和是否应改用容器成员函数。

29.1 binary_search

std::binary_search 把一个已分区区间和一个目标值转换成布尔判断。它的输出只有 true 或 false，因此它适合回答“等价元素是否存在”，并且不携带元素位置、重复数量、插入点或稳定边界。

在贯穿材料中，std::binary_search(prices.begin(), prices.end(), 101) 返回 true。这个结果来自两个比较方向共同定义的等价关系：某个元素 x 与 target 等价，条件是 x < target 为假，并且 target < x 也为假。使用自定义比较器时，同一个关系写成 !comp(x, target) && !comp(target, x)。这里的“等价”来自排序关系，并不要求 operator== 返回 true。

这个区别会直接影响工程代码。价格表中如果元素类型改成结构体，比较器只比较 price 字段，那么 std::binary_search 查到的是“存在一个价格等价的记录”，而不是“存在一个字段完全相同的对象”。下面的例子用最小代码暴露这个边界。

#include <algorithm>
#include <string>
#include <vector>

struct Quote {
    int price;
    std::string venue;
};

int main() {
    std::vector<Quote> quotes{{100, "A"}, {101, "B"}, {101, "C"}, {103, "D"}};

    auto by_price = [](const Quote& lhs, const Quote& rhs) {
        return lhs.price < rhs.price;
    };

    bool has_price_101 = std::binary_search(
        quotes.begin(), quotes.end(), Quote{101, "X"}, by_price
    );
}

has_price_101 的含义是存在某个 Quote 的 price 与 101 处在同一个比较等价类。venue 没有进入比较器，所以 "A"、"B"、"C" 或 "X" 的差异不会改变二分判断。读源码或排查业务问题时，应先找 comparator 定义的排序键，再解释 binary_search 的结果。

标准库常见实现形状通常把 binary_search 建立在 lower_bound 之上：先定位第一个不小于 value 的位置，再检查这个位置与 value 是否互不小于。这个形状说明 binary_search 并不比 lower_bound 多出定位能力；它只是把定位结果压缩成布尔值。

template<class ForwardIt, class T, class Compare>
bool mini_binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp) {
    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first);
}

这段简化代码只服务于理解算法关系。真实标准库实现会处理更多模板、constexpr、ranges、投影和调试细节。读者需要保留的结论是：当后续逻辑需要位置、插入点或重复范围时，直接调用 lower_bound 或 equal_range，可以减少一次从 bool 反向推回位置的设计错误。

29.2 lower_bound

std::lower_bound 返回第一个不排在目标值之前的位置。默认比较下，它返回第一个满足 *it < value 为假的迭代器；自定义比较器下，它返回第一个满足 comp(*it, value) 为假的迭代器。这个位置同时承担两个角色：已存在元素的左边界，以及保持有序性时可以插入目标值的最早位置。

贯穿材料中，prices 为 {100, 100, 101, 101, 101, 103, 106}，lower_bound(..., 101) 返回下标 2。下标 0 和 1 的元素满足 price < 101，从下标 2 开始该表达式为假。算法寻找的边界就是布尔序列从 true 到 false 的第一次切换。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

auto first_101 = std::lower_bound(prices.begin(), prices.end(), 101);
auto insert_102 = std::lower_bound(prices.begin(), prices.end(), 102);

auto index_101 = first_101 - prices.begin();   // 2
auto index_102 = insert_102 - prices.begin();  // 5

insert_102 返回下标 5，因为 101 < 102 对前三个 101 都为真，而 103 < 102 为假。这个位置前方的元素都能排在 102 前面，后方的元素都不会排在 102 前面，所以把 102 插入下标 5 可以保持升序。

lower_bound 的工程价值通常超过存在性查询。它能直接回答“排名”“第一个可处理记录”“第一个不早于某时间点的事件”“第一个容量不低于需求的桶”等边界问题。只要业务问题能写成“前半段满足某个比较表达式，后半段不满足”，lower_bound 就比手写循环更接近标准语义。

比较器方向需要精确核对。lower_bound(first, last, value, comp) 调用的是 comp(element, value)，因此比较器必须能把元素放到目标值前方。对于异构查找，例如 std::vector<std::string> 中用 std::string_view 查询，比较器的参数类型要覆盖“元素在左、目标在右”的调用方向。C++20 ranges 版本还加入 projection，可以把“先取字段再比较”的动作显式写入算法参数；传统算法中通常通过 comparator 或临时 key 对象表达同一件事。

29.3 upper_bound

std::upper_bound 返回第一个排在目标值之后的位置。默认比较下，它返回第一个满足 value < *it 为真的迭代器；自定义比较器下，它返回第一个满足 comp(value, *it) 为真的迭代器。它和 lower_bound 使用相反的比较方向，因此它定位的是等价区间的右边界后一个位置。

贯穿材料中，upper_bound(..., 101) 返回下标 5。下标 2、3、4 的元素与 101 等价，101 < 101 为假；下标 5 的元素是 103，101 < 103 为真，于是下标 5 成为右边界。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

auto first = std::lower_bound(prices.begin(), prices.end(), 101);
auto last = std::upper_bound(prices.begin(), prices.end(), 101);

auto count = last - first;  // 3

这段代码把重复元素数量转换成两个边界的距离。对随机访问迭代器，last - first 是常数时间；对 forward iterator，需要使用 std::distance(first, last)，距离计算本身会线性步进。算法复杂度描述中的“比较次数对数级”并不覆盖所有 iterator 操作成本。

upper_bound 也常用于稳定插入策略。若希望新来的等价元素插入到已有等价元素之后，使用 upper_bound 作为插入位置；若希望插在已有等价元素之前，使用 lower_bound。这个选择不会改变有序性，但会改变等价元素内部的相对布局。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

prices.insert(std::upper_bound(prices.begin(), prices.end(), 101), 101);
// 结果仍然升序，新 101 位于原有 101 之后。

这个例子同时暴露容器成本。upper_bound 查找阶段对 std::vector 是对数级比较和对数级位置跳转；insert 阶段可能移动插入点之后的元素，并可能触发扩容。二分算法只优化定位，不消除顺序容器中间插入的移动成本。

29.4 equal_range

std::equal_range 一次返回等价元素的半开区间 [first, second)。第一个迭代器对应 lower_bound，第二个迭代器对应 upper_bound。当目标值存在时，这个区间覆盖所有等价元素；当目标值缺席时，两个迭代器相等，并且共同指向合法插入点。

贯穿材料中，equal_range(..., 101) 返回 [2, 5)；equal_range(..., 102) 返回 [5, 5)。前者说明有三个等价元素，后者说明 102 缺席且应该插在下标 5。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

for (int key : {101, 102}) {
    auto [first, last] = std::equal_range(prices.begin(), prices.end(), key);
    auto begin_index = first - prices.begin();
    auto end_index = last - prices.begin();
    auto count = last - first;
}

equal_range 适合把“查找重复键”转换成范围处理。日志按时间戳排序时，查找同一秒内的所有记录；订单按价格排序时，取出同一价格的所有订单；索引按用户 ID 排序时，定位某个用户的所有事件，都可以用同一个边界模型表达。

比较器一致性在 equal_range 中更容易暴露问题。它同时依赖 comp(element, value) 和 comp(value, element) 两个方向。如果排序时使用一个比较器，查询时换成另一个比较器，或者比较器内部依赖会变化的全局状态，区间相对查询表达式的分区前提就会被破坏。结果层面可能表现为遗漏元素、范围过宽、范围过窄或调试版本断言失败；标准语义层面，这类调用已经越过算法前提。

equal_range 与关联容器成员函数也要分清。对 std::vector、std::deque、std::array 这类随机访问或近似连续存储的有序区间，算法版本能直接工作。对 std::map、std::set、std::multimap、std::multiset 这类树形容器，成员 equal_range 能沿树结构做对数级节点跳转；算法版本拿到的是双向迭代器，比较次数仍是对数级，迭代器步进可能线性。容器知道自己的树结构，泛型算法只知道 iterator 表面。

29.5 partition_point

std::partition_point 把二分查找从“有序值比较”推广到“单调谓词分区”。它要求区间前半段都满足谓词，后半段都不满足谓词，并返回两个分区之间的第一个位置。这个算法从 C++11 进入标准库，C++20 起可在常量求值语境中使用。

贯穿材料里，lower_bound(prices, 101) 可以写成 partition_point：谓词是 price < 101。所有小于 101 的元素位于前半段，所有不小于 101 的元素位于后半段，分界点就是 lower_bound 的返回值。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

auto first_101 = std::partition_point(
    prices.begin(), prices.end(),
    [](int price) { return price < 101; }
);

这个写法说明二分的核心对象不是“中间元素是否等于目标值”，而是“谓词结果是否从真切换到假”。一旦问题能形成这种单调布尔序列，二分边界就可以成立。比如排好序的容量表中找第一个容量不低于需求值，时间线中找第一个不早于截止时间的事件，版本列表中找第一个包含某修复的版本，都属于分界点问题。

partition_point 的前提比“排序”更抽象。下面的区间按奇偶分区，但数值没有整体升序；它仍然适合 partition_point，因为谓词 x % 2 == 0 的结果在区间中先全真后全假。

std::vector<int> values{8, 2, 6, 4, 5, 3, 7, 1};

auto first_odd = std::partition_point(
    values.begin(), values.end(),
    [](int x) { return x % 2 == 0; }
);

first_odd 指向 5。这个例子不能推出 lower_bound 可以在任意分区上查找某个值，因为 lower_bound 的谓词来自比较表达式 element < value。它能推出的结论是：二分边界算法真正依赖的是“相对当前谓词的单调分区”。排序区间只是最常见、最容易复用的一种分区来源。

29.6 前提条件：已排序区间

二分查找算法的有效输入是相对当前比较表达式已经分区的区间。实际工程中通常通过排序得到这种分区：若区间按同一个 comparator 升序排列，那么对任意目标值，表达式 comp(element, value) 会先为真后为假，表达式 comp(value, element) 会先为假后为真，于是 lower_bound、upper_bound、equal_range 和 binary_search 都能成立。

前提检查不能只看“肉眼上像升序”。排序时使用的比较规则、查询时使用的比较规则、目标值类型、投影字段和对象可变性都属于同一个契约。下面这段代码中，数据按 price 排序，查询也按 price 比较，因此契约闭合。

struct Quote {
    int price;
    int sequence;
};

std::vector<Quote> quotes{{100, 1}, {101, 2}, {101, 3}, {103, 4}};

auto by_price = [](const Quote& lhs, const Quote& rhs) {
    return lhs.price < rhs.price;
};

auto range = std::equal_range(
    quotes.begin(), quotes.end(), Quote{101, 0}, by_price
);

若排序时按 price，查询时按 sequence，区间对查询表达式不再保证分区。此时算法内部每一步仍会比较和推进，但返回值没有标准语义保证。排查这类问题时，先把每个元素代入查询表达式，写出一串布尔值。如果它不是若干个 true 后接若干个 false，lower_bound 的前提就已经被破坏。

重复元素也依赖等价关系稳定。comp(a, b) 和 comp(b, a) 都为假时，a 与 b 处在同一个等价类。等价类内部可以有多个对象，但这些对象在排序键上必须连续出现。equal_range 返回的范围正是这个连续等价类；若比较器不满足严格弱序，排序算法和二分算法都失去共同基础。

可变元素会破坏已排序区间。把对象放入 std::vector 并排序后，如果后续直接修改参与比较的字段，原区间的排序事实随之失效。对 std::set 这类有序关联容器，key 通过迭代器暴露为不可修改形式，目的就是保护树形有序不变量。对顺序容器，编译器不会阻止修改排序键，调用者需要在修改后重新排序或重新建立索引。

工程判断顺序可以固定为四步：第一，确认排序或分区使用的表达式；第二，把目标值代入该表达式，检查布尔序列是否单调；第三，确认 comparator 不依赖会变化的外部状态；第四，确认元素在查询前没有修改排序键。四步都成立时，二分算法结果才有可解释的标准语义。

29.7 lower_bound 底层实现

lower_bound 的最小实现可以整理成四个状态：first 表示当前候选区间起点，count 表示候选区间长度，step 表示一半长度，it 表示本轮中点。每一轮比较 *it 与 value 后，要么丢弃左半段和中点，要么保留左半段。循环结束时，first 就是第一个不小于目标值的位置。

下面的简化代码接近标准库常见实现形状，使用 std::distance 和 std::advance 支持 forward iterator。它展示的是算法骨架，不代表某个具体实现文件中的源码。

#include <iterator>

template<class ForwardIt, class T, class Compare>
ForwardIt mini_lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp) {
    using difference_type = typename std::iterator_traits<ForwardIt>::difference_type;

    difference_type count = std::distance(first, last);

    while (count > 0) {
        ForwardIt it = first;
        difference_type step = count / 2;
        std::advance(it, step);

        if (comp(*it, value)) {
            first = ++it;
            count -= step + 1;
        } else {
            count = step;
        }
    }

    return first;
}

这段代码的循环不变量是：答案一定位于当前 [first, first + count) 候选区间中。若 comp(*it, value) 为真，*it 以及它之前的元素都排在目标值之前，答案只能在 it 之后，所以 first = ++it，长度减去左半段和中点。若该表达式为假，it 可能就是答案，右半段可以丢弃，于是长度收缩为 step。

对贯穿材料执行 lower_bound(..., 101) 时，候选区间长度从 7 开始。第一次取中点下标 3，元素是 101，101 < 101 为假，保留左半段 [0, 3)。第二次取中点下标 1，元素是 100，100 < 101 为真，丢弃 [0, 2)，候选区间变成 [2, 3)。第三次检查下标 2，元素是 101，表达式为假，最后返回下标 2。

这个实现形状解释了两个常见现象。第一，二分返回的是边界位置，不需要命中一个等于目标的中点。第二，区间长度每轮大约减半，所以比较次数对数级；但每次构造中点需要 iterator 前进 step，这个动作的成本由 iterator category 决定。

源码阅读时应抓住这一条主线：长度由 distance 初始化，中点由 advance 或随机访问加法得到，比较表达式决定丢弃哪一半，返回值是最终的 first。模板包装、concept 约束、debug iterator、ranges 投影和 constexpr 修饰都服务于接口适配；算法不变量仍然是这四个状态之间的关系。

29.8 iterator category 对复杂度的影响

二分查找的复杂度需要拆成比较次数和迭代器步进次数。标准描述保证比较次数为对数级，但对非随机访问迭代器，寻找中点需要反复线性推进，整体 iterator increment 次数可能是线性的。这个边界决定了同一个 lower_bound 在 std::vector 和 std::list 上呈现不同成本结构。

std::vector 的迭代器是随机访问迭代器。算法可以用 first + step 或等价方式跳到中点，距离计算和中点定位都能高效完成。因此有序 std::vector 上的 lower_bound 通常是二分算法最典型的适用场景：内存连续、比较次数少、定位动作快。

std::list 的迭代器是双向迭代器，满足 forward iterator 要求，因此算法版本可以编译运行。但 std::advance(it, step) 需要沿链表逐节点移动，候选区间每轮减半并不会让节点步进变成对数级。对链表做算法版本二分，经常得到“比较次数少，指针追踪多”的结果；对性能敏感路径，应改用更合适的数据结构，而不是期待二分抵消链表访问模式。

关联容器的情况更容易误判。std::set<int> 中的元素已经有序，但它的迭代器不是随机访问迭代器。调用 std::lower_bound(s.begin(), s.end(), key) 会通过迭代器表面寻找中点；调用 s.lower_bound(key) 会沿树结构按比较结果向左或向右走。两者的标准语义都能给出边界位置，成本来源不同，工程上通常应选择成员函数。

#include <algorithm>
#include <set>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 4, 8, 16, 32};
    std::set<int> s{1, 2, 4, 8, 16, 32};

    auto a = std::lower_bound(v.begin(), v.end(), 8); // 适合随机访问区间
    auto b = s.lower_bound(8);                        // 适合树形容器
}

选择顺序可以固定下来。若数据存放在连续有序区间中，优先考虑算法版本二分。若数据存放在有序关联容器中，优先考虑容器成员查找。若数据在链表或 forward-only range 中，先重新审视容器选择，再决定是否保留算法版本二分。若数据需要频繁插入并保持有序，查找成本和维护有序性的移动、分配、节点成本要一起估算。

最终的工程结论是：二分算法优化的是“根据比较结果缩小候选范围”的次数，底层迭代器决定“到达中点”的成本。把这两个维度分开，才能解释为什么同一个标准算法在不同容器上有不同性能表现。

最小自检任务

阅读下面代码，判断四个问题：has_101 的含义是什么；range_101 覆盖哪些下标；range_102 为什么是空区间；把最后一行改成 std::lower_bound(s.begin(), s.end(), 101) 后，标准语义和工程成本分别如何变化。

#include <algorithm>
#include <set>
#include <vector>

int main() {
    std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

    bool has_101 = std::binary_search(prices.begin(), prices.end(), 101);
    auto range_101 = std::equal_range(prices.begin(), prices.end(), 101);
    auto range_102 = std::equal_range(prices.begin(), prices.end(), 102);

    std::set<int> s{100, 101, 103, 106};
    auto pos = s.lower_bound(101);
}

答案要点

has_101 表示区间中存在与 101 比较等价的元素，等价由排序关系定义。range_101 覆盖下标 [2, 5)，因为下标 2 是第一个不小于 101 的位置，下标 5 是第一个大于 101 的位置。range_102 是 [5, 5)，因为 102 缺席，且下标 5 是保持升序的插入点。

std::set 的成员 lower_bound 沿树结构查找，能利用容器内部节点关系。把它改成算法版本 std::lower_bound(s.begin(), s.end(), 101) 后，返回位置的标准语义仍是第一个不小于 101 的元素；工程成本会变差，因为算法只看到双向迭代器，寻找中点需要线性步进。正确判断顺序是先确认分区前提，再选择边界算法，最后按 iterator category 和容器内部结构估算成本。

本章知识点总结

• 分区前提：二分查找算法要求区间相对当前比较表达式形成单调分区，排序只是最常见的分区来源。
• 存在性查询：binary_search 返回布尔值，含义是存在与目标值比较等价的元素。
• 等价定义：两个对象互不排在对方之前时处于同一个比较等价类，判断依据来自 comparator。
• 左边界：lower_bound 返回第一个不排在目标值之前的位置，也可作为最早合法插入点。
• 右边界：upper_bound 返回第一个排在目标值之后的位置，也可作为等价元素之后的插入点。
• 等价范围：equal_range 返回 [lower_bound, upper_bound)，可直接表示重复键的连续范围。
• 缺席插入点：目标值缺席时，equal_range 的两个迭代器相等，并共同指向合法插入位置。
• 谓词分界：partition_point 定位谓词结果从真切换到假的位置，是 lower_bound 思想的泛化。
• 比较器一致：排序、查询和等价判断必须使用一致的比较规则，变化的外部状态会破坏分区契约。
• 实现骨架：lower_bound 的核心状态是 first、count、step 和中点迭代器，循环通过比较结果丢弃一半候选区间。
• 比较次数：二分算法把比较次数控制在对数级，这一承诺不等于所有 iterator 操作都是对数级。
• 步进成本：非随机访问迭代器寻找中点可能产生线性步进，链表和树形容器需要单独估算。
• 成员优先：有序关联容器应优先使用成员 lower_bound、upper_bound 和 equal_range，因为成员函数能利用树结构。
• 选型顺序：先验证分区前提，再选择存在性或边界算法，接着检查 comparator 方向，最后估算容器和迭代器成本。