STL 二分查找 lower_bound 与 upper_bound 详解

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

总结：如何选择？