lower_bound & upper_bound
这两个函数是为了支持随机访问迭代器而设计的。
1. lower_bound
模版结构
// 查找第一个【大于或等于】value 的位置
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
- first / last: 搜索范围（必须是有序序列）。
- value: 要查找的目标值。
- 返回值：返回一个指向该元素的迭代器；如果找不到，则返回 last。
操作示例
vector<int> v = {1, 2, 4, 4, 4, 6, 7};
// 查找第一个 >= 4 的位置
auto it_low = std::lower_bound(v.begin(), v.end(), 4);
// 指向第一个 4 的下标（下标 2）
2. upper_bound
模版结构
// 查找第一个【严格大于】value 的位置
template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);
- first / last: 搜索范围（必须是有序序列）。
- value: 要查找的目标值。
- 返回值：返回一个指向该元素的迭代器；如果找不到，则返回 last。
操作示例
vector<int> v = {1, 2, 4, 4, 4, 6, 7};
// 查找第一个 > 4 的位置
auto it_up = std::upper_bound(v.begin(), v.end(), 4);
// 指向数字 6 的下标（下标 5）
3. 关联容器的成员函数
特别注意
对于有序关联容器，必须使用其自带的成员函数，而非全局算法。
核心差异
虽然全局的 std::lower_bound 也能处理 set 或 map，但因为关联容器的迭代器不支持随机访问，全局算法会退化为线性查找 O(N)。而成员函数版本利用红黑树的特性，能保证对数查找 O(log N)。
常用容器接口
// 以 std::set 为例
iterator lower_bound(const Key& key);
iterator upper_bound(const Key& key);
// 以 std::map 为例（仅针对 Key 进行查找）
iterator lower_bound(const Key& key);
iterator upper_bound(const Key& key);
操作示例：std::set
set<int> s = {10, 20, 30, 40, 50};
// 查找第一个 >= 25 的元素
auto it_low = s.lower_bound(25); // 指向 30
// 查找第一个 > 30 的元素
auto it_up = s.upper_bound(30); // 指向 40
操作示例：std::map
在 map 中，这两个函数只检查 Key。
std::map<int, string> m = {{1, "apple"}, {3, "banana"}, {5, "cherry"}};
auto it = m.lower_bound(2); // 返回迭代器指向 {3, "banana"}，因为 3 是第一个 >= 2 的键
4. 进阶：equal_range
如果你需要同时获取 lower_bound 和 upper_bound（例如在 multiset 中找出所有等于某个值的区间），可以使用 equal_range。
模版结构
// 返回一个 pair，包含 [lower_bound, upper_bound)
std::pair<iterator, iterator> equal_range(const Key& key);
实际应用
std::multiset<int> ms = {1, 2, 2, 2, 3};
auto range = ms.equal_range(2);
// range.first -> 指向第一个 2
// range.second -> 指向数字 3 (第一个严格大于 2 的位置)
// 距离即为元素个数
auto count = std::distance(range.first, range.second); // 结果为 3
总结：如何选择？
| 容器类型 | 推荐函数 | 时间复杂度 |
|---|---|---|
| vector / array / deque | std::lower_bound | O(log N) |
| set / map / multiset / multimap | container.lower_bound() | O(log N) |
| list | std::lower_bound | O(N) (不推荐对 list 频繁二分) |
| unordered_set/unordered_map | 不支持 (无序容器没有边界概念) | N/A |
