关于STL中的二分(lower_bound&upper_bound)

lower_bound&upper_bound

这两个函数是为了支持随机访问随机访问迭代器而设计的。

1.lower_bound

模版结构

// 查找第一个【大于或等于】value 的位置template<classForwardIt,classT> 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<classForwardIt,classT> 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(N)O(N)。而成员函数版本利用红黑树的特性，能保证对数查找 O(log⁡N)O(\log N)O(logN)。

常用容器接口

// 以 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

总结：如何选择？