前言
在处理 $O(N \log N)$ 复杂度的算法（如最长上升子序列 LIS）时，std::vector 的二分查找函数是核心工具。本课件将带你从底层工具“迭代器”开始，逐步掌握其高级用法。
第一部分：迭代器（Iterator）基础
1. 什么是迭代器？
迭代器是一种抽象的“指针”。它的作用是让你能够遍历容器（如 vector, set, list）中的元素，而不需要关心容器的底层结构。
- 形象理解：如果容器是一个一排房间的走廊，迭代器就是站在某个门前的“导游”，他可以告诉你房里的东西（解引用），也可以走到下一个房间（自增）。
2. 核心操作与内存模型
对于 std::vector<int> v，C++ 采用左闭右开的区间表示法：$[begin, end)$。
v.begin()：返回指向第一个元素的迭代器。v.end()：返回指向最后一个元素之后（Past-the-end）位置的迭代器。它是一个“哨兵”，不指向任何实际数据。*it（解引用）：获取迭代器当前指向的元素值。如*v.begin()等价于v[0]。it++/it--：将导游移动到上一个或下一个房间。
3. 代码示例
vector<int> v = {10, 20, 30};
// 使用 auto 自动推导迭代器类型
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << " "; // 输出 10 20 30
}
第二部分：二分查找的前提条件
在使用 lower_bound 和 upper_bound 之前，必须满足一个核心前提：
序列必须是有序的。
如果序列无序，这两个函数将无法正常工作，返回的结果将是错误的。
第三部分：std::lower_bound 详解
1. 功能描述
在有序范围内查找第一个大于等于（$\ge$）给定值 val 的位置。
2. 函数语法与参数含义
auto it = lower_bound(first, last, val);
- 参数 1：
first- 含义：查找范围的起始位置迭代器（包含此位置）。
- 通常传入：
v.begin()。
- 参数 2：
last- 含义：查找范围的终止位置迭代器（不包含此位置）。
- 通常传入：
v.end()。
- 参数 3：
val- 含义：待查找的目标值。
- 逻辑：寻找第一个满足
element >= val的元素。
3. 返回值逻辑
- 成功：返回指向第一个 $\ge val$ 的元素的迭代器。
- 失败：如果范围内所有元素都小于
val，返回last（即v.end()）。
第四部分：std::upper_bound 详解
1. 功能描述
在有序范围内查找第一个严格大于（$>$）给定值 val 的位置。
2. 函数语法与参数含义
auto it = upper_bound(first, last, val);
- 参数 1：
first- 含义：查找范围的起始位置。
- 参数 2：
last- 含义：查找范围的结束位置（不含）。
- 参数 3：
val- 含义：待查找的目标值。
- 逻辑：寻找第一个满足
element > val的元素。
3. 返回值逻辑
- 成功：返回指向第一个 $> val$ 的元素的迭代器。
- 失败：如果没有任何元素大于
val，返回last（即v.end()）。
第五部分：直观对比与总结
假设有一个有序数组 v = {1, 2, 4, 4, 4, 6, 7}，查找数值 4：
| 函数 | 查找目标 | 结果指向的元素 | 结果下标 (it - v.begin()) |
|---|---|---|---|
lower_bound |
$\ge 4$ | 第一个 4 |
2 |
upper_bound |
$> 4$ | 元素 6 |
5 |
关键差异总结：
- 相等情况：
lower_bound会停在等于val的第一个元素上；而upper_bound会跳过所有等于val的元素，停在更大的元素上。 - 区间确定：所有等于 $x$ 的元素区间为：
[lower_bound(x), upper_bound(x))。
第六部分：实战技巧
1. 如何获取下标？
由于 vector 的迭代器支持算术运算，通过将结果迭代器减去 v.begin() 即可得到从 $0$ 开始的下标：
int pos = lower_bound(v.begin(), v.end(), val) - v.begin();
2. 如何修改值？（如 LIS 算法中所用）
如果你想替换掉查找到的那个位置的值，直接对迭代器进行解引用赋值：
auto it = lower_bound(f.begin(), f.end(), a[i]);
if (it != f.end()) {
*it = a[i]; // 找到位置后，用更小的 a[i] 覆盖原有的值
}
3. 复杂度与性能
- 时间复杂度：二分查找为 $O(\log N)$。
- 注意：对于
std::set或std::map，请务必使用成员函数s.lower_bound()，因为全局算法在非随机访问容器上会退化为 $O(N)$。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
