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';
}
运行后 exists 为 true,target == 101 的等价元素占据半开区间 [2, 5):first 与 range.first 均指向下标 2,last 与 range.second 均指向下标 5。
关键事实
C++ 标准 [alg.binary.search] 将以下算法统一定义在“区间已相对比较表达式分区”的前提之上:仅保证比较次数为对数级,不保证非随机访问迭代器的步进次数为对数级(参见 C++ draft binary search algorithms 与 cppreference binary search operations)。
| 算法 | 返回值 | 判定条件(自定义 comp) | 贯穿示例(target = 101) | 典型用途 |
|---|---|---|---|---|
std::binary_search | bool | 存在元素满足 !comp(*it, val) && !comp(val, *it) | true | 仅确认等价元素是否存在 |
std::lower_bound | 迭代器 | 首个使 comp(*it, val) 为假的位置 | 下标 2 | 左边界、最早合法插入点 |
std::upper_bound | 迭代器 | 首个使 comp(val, *it) 为真的位置 | 下标 5 | 右边界后一位置、稳定尾插点 |
std::equal_range | std::pair<It, It> | {lower_bound, upper_bound} | [2, 5) | 一次取全等价范围或缺席插入点 |
std::partition_point | 迭代器 | 首个使一元谓词 pred(*it) 为假的位置 | 下标 2(p < 101) | 任意单调布尔分区的分界点 |
29.1 binary_search
std::binary_search 将已分区区间与目标值压缩为 bool 结果,仅回答“等价元素是否存在”,不携带位置、重复数量、插入点或稳定边界。
结构体按单字段排序查找时,这一语义差异会直接暴露:下例中 by_price 只比较 price,忽略 venue。
#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 为 true,仅说明区间存在 price == 101 的记录,与 venue 是否为 "X" 无关。排查业务代码时,应先看比较器抽取的排序键,再解释结果。
边界与误区
排序等价 ≠ operator== 相等:std::binary_search 判定等价的条件是 x < target 与 target < x 同为假(即 !comp(x, target) && !comp(target, x))。只要比较器未纳入全部字段,其余字段不同的对象也会落入同一等价类。
标准库通常将 binary_search 直接实现在 lower_bound 之上:先找首个不小于 value 的位置,再校验双方是否互不小于。
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);
}
可见 binary_search 并不比 lower_bound 多出定位能力;只要后续逻辑需要下标、计数或插入点,直接调用 lower_bound 或 equal_range,可避免从 bool 反向重算位置的错误。
29.2 lower_bound
std::lower_bound 返回首个不排在目标值之前的位置(默认比较下 *it < value 为假,自定义比较器下 comp(*it, value) 为假)。它同时充当两个角色:已存在等价元素的左边界,以及保持有序的最早合法插入点。
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
- 查找
101:下标0、1满足price < 101(true),从下标2起切换为false,故左边界在下标2。 - 查找
102:前五个元素均满足price < 102,直到下标5(103)才切换为false,故将102插在下标5可保持升序。
只要工程查询能抽象为“前段满足比较条件、后段不满足”,lower_bound 就可直接替代手写二分:
- 定位排名与阈值:查找第一个不低于目标分数或阈值的记录。
- 时间线截断:定位第一个不早于指定时间戳的事件。
- 资源分桶:匹配第一个容量不低于需求的桶。
关键事实
std::lower_bound(first, last, value, comp) 始终按 comp(*it, value)(区间元素在左、目标值在右)调用。若需异构查找(如在 std::vector<std::string> 中用 std::string_view 查询),比较器必须支持“左元素、右目标”的参数类型(或使用透明比较器 std::less<>);C++20 std::ranges::lower_bound 还支持传入 projection 直接提取字段,避免构造临时哑对象。
29.3 upper_bound
std::upper_bound 返回首个排在目标值之后的位置(默认比较下 value < *it 为真,自定义比较器下 comp(value, *it) 为真)。在贯穿材料中,upper_bound(..., 101) 跳过全部等价的 101(101 < 101 为假),停在首个使 101 < 103 为真的下标 5。
| 算法 | 自定义比较器判别式 | 返回边界语义 | 重复键插入顺序 |
|---|---|---|---|
std::lower_bound | 首个使 comp(*it, value) 为假 | 等价区间左边界 | 新元素插在已有等价元素之前 |
std::upper_bound | 首个使 comp(value, *it) 为真 | 等价区间右边界后一位置 | 新元素插在已有等价元素之后 |
组合两个边界可直接计算重复元素数量,或用于保持同键相对顺序的稳定尾插:
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
prices.insert(std::upper_bound(prices.begin(), prices.end(), 101), 101);
// 结果仍然升序,新 101 位于原有 101 之后。
边界与误区
last - first 仅对随机访问迭代器是常数时间;若区间为前向迭代器,用 std::distance(first, last) 计数仍需线性步进。此外,二分只优化定位阶段,向 std::vector 中间 insert 仍会搬移插入点后的元素并可能触发扩容。
29.4 equal_range
std::equal_range 一次返回等价元素的半开区间 [first, second),其中 first 等价于 lower_bound,second 等价于 upper_bound。目标值存在时返回全部等价元素范围;缺席时两个迭代器相等,共同指向合法插入点。
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;
}
贯穿材料中,101 返回 [2, 5)(共 3 个等价元素),102 返回 [5, 5)(缺席且应插在下标 5)。该模型可直接用于提取有序日志中的同秒记录、同价位订单或同用户事件。
边界与误区
双向比较器一致性:std::equal_range 会同时调用 comp(*it, value) 与 comp(value, *it)。若建表排序与查询比较器不一致、异构比较器只重载了单向参数顺序,或比较器依赖会变化的外部状态,分区前提即被破坏,轻则范围错位或遗漏元素,重则触发调试断言失败。
对 std::map、std::set、std::multimap、std::multiset 等树形关联容器,应优先调用成员函数 equal_range 而非同名泛型算法(原因见 29.8 节)。
29.5 partition_point
std::partition_point 将二分查找从“有序值比较”泛化为“单调一元谓词分区”:只要前半段全部满足 pred(*it)、后半段全部不满足,它就返回首个使 pred(*it) 为假的位置(C++11 引入,C++20 起支持 constexpr)。
在贯穿材料中,lower_bound(..., 101) 等价于以 price < 101 为谓词调用 partition_point:
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; }
);
即使数据整体并未按大小排序,只要相对某个谓词先全真后全假,分界点依然成立。下例中 {8, 2, 6, 4, 5, 3, 7, 1} 按奇偶分区,first_odd 精准指向 5:
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; }
);
核心判断
二分查找定位的不是“等于目标的中点”,而是布尔序列从 true 切换到 false 的唯一边界。有序区间只是最常复用的分区来源;反过来,仅按谓词分区而未按值排序的区间不能调用 lower_bound,因为后者固定依赖比较表达式 comp(*it, value)。
29.6 前提条件:已排序区间
二分算法的真正前提是“区间已相对当前比较表达式分区”。若区间按同一 comp 升序排列,对任意目标值都会满足 comp(*it, value) 先真后假、comp(value, *it) 先假后真,契约才能闭合。下例中建表与查询均以 by_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比较,区间对查询表达式不再单调,返回值无标准语义保证。 - 非严格弱序:比较器破坏严格弱序会导致同键元素分散、等价类不再连续,
equal_range的半开区间模型随之失效。 - 排序后原地改键:
std::set通过迭代器将键暴露为const以守住有序不变量;而std::vector排序后若原地修改键字段,有序性会静默失效,调用方必须重排或重建索引。
排查顺序
- 核对规则:确认建表排序与本次查询使用同一个比较表达式。
- 还原布尔序列:将元素逐一代入查询表达式,验证结果是否呈“连续
true后接连续false”。 - 检查严格弱序:确认比较器满足严格弱序,且不依赖可变全局状态。
- 排查原地修改:确认顺序容器元素在排序后未修改参与比较的键字段。
29.7 lower_bound 底层实现
lower_bound 的核心骨架围绕四个状态推进:候选起点 first、候选长度 count、步长 step 与中点 it。算法通过 std::distance 与 std::advance 支持前向迭代器:
#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及其左侧元素全部排在目标之前,必不是答案,故令first = ++it并减去左半段与中点(count -= step + 1)。comp(*it, value)为假:it本身可能就是答案,仅丢弃右半段,收缩长度为count = step。
在贯穿材料 {100, 100, 101, 101, 101, 103, 106} 上执行 lower_bound(..., 101) 的收缩过程如下:
| 轮次 | 候选区间 [first, first + count) | count | step | 中点 it 及元素 | comp(*it, 101) | 区间更新 |
|---|---|---|---|---|---|---|
| 1 | [0, 7) | 7 | 3 | 下标 3(101) | false | count = 3 → [0, 3) |
| 2 | [0, 3) | 3 | 1 | 下标 1(100) | true | first = 2, count = 1 → [2, 3) |
| 3 | [2, 3) | 1 | 0 | 下标 2(101) | false | count = 0 → 返回下标 2 |
核心判断
lower_bound 找的是分界点,不要求中点命中等于目标的值;每轮 count 减半只把比较次数压到对数级,而构造中点时 std::advance(it, step) 的移动成本完全由底层迭代器类别决定。
29.8 iterator category 对复杂度的影响
评估二分查找性能必须拆开两个维度:比较次数与迭代器步进 / 节点跳转次数。标准仅承诺比较次数为对数级,而不同容器到达中点的方式截然不同:
| 容器 / 区间类型 | 迭代器类别 | 调用方式 | 比较次数 | 步进 / 跳转成本 | 工程结论 |
|---|---|---|---|---|---|
std::vector / std::deque / std::array | 随机访问 | std::lower_bound 等泛型算法 | 对数级 | 对数级(+ step 常数跳转) | 最典型适用场景,连续内存缓存友好 |
std::set / std::map 等关联容器 | 双向 | 成员函数 c.lower_bound(k) 等 | 对数级 | 对数级(沿树节点跳转) | 必须优先选用成员函数 |
std::set / std::map 误用泛型算法 | 双向 | std::lower_bound(c.begin(), ...) | 对数级 | 线性级(advance 逐节点步进) | 语义相同但丢失树结构跳转优势 |
std::list / std::forward_list | 双向 / 前向 | 泛型算法(不推荐) | 对数级 | 线性级(逐节点指针追踪) | 少比较无法抵消遍历成本,应换容器 |
#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); // 适合树形容器
}
核心判断
二分算法只优化“缩小候选区间时的比较次数”,迭代器能力才决定“到达中点”的真实开销:连续有序区间用泛型算法,树形关联容器用成员函数,链表类容器先重构数据结构;若场景需高频插入并维持有序,还应把顺序容器元素搬移与节点分配成本一并计入。
最小自检任务
阅读下面代码,判断四个问题:
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);
}
本章知识点总结
- 分区前提
二分算法依赖区间对当前比较表达式呈单调布尔分区(先
true后false);排序与查询比较器错配、破坏严格弱序或原地修改键字段都会破坏契约。 - 存在性与等价
std::binary_search仅返回bool,等价由排序关系!comp(x, val) && !comp(val, x)而非operator==定义;需要位置或计数时应直接选用lower_bound或equal_range。 - 左右边界与插入点
std::lower_bound定位首个使comp(*it, val)为假的位置(左边界 / 最早插入点),std::upper_bound定位首个使comp(val, *it)为真的位置(右边界后一位置 / 稳定尾插点)。 - 等价范围与双向一致
std::equal_range一次返回[lower_bound, upper_bound)(缺席时为[pos, pos));因其同时调用comp(*it, val)与comp(val, *it),自定义及异构比较器必须保证双向一致。 - 谓词分界泛化
std::partition_point定位任意单调一元谓词从true切到false的位置,不要求区间按值有序,但仅按谓词分区的区间不能反推调用lower_bound。 - 骨架与隐性成本
lower_bound通过收缩[first, first + count)定位分界点,仅保证比较次数为对数级;非随机访问迭代器上的std::advance定位中点及std::distance计数均呈线性成本。 - 容器与接口选型
连续有序区间优先用泛型算法;
std::set/std::map等关联容器必须优先用成员函数lower_bound/upper_bound/equal_range;链表类容器应先重审数据结构再谈二分。