详解lower_bound和upper_bound

### STL 容器 `map` 中 `lower_bound` 和 `upper_bound` 函数详解及二分查找原理 #### 什么是 `lower_bound` 和 `upper_bound` 在 C++ 的 STL 中，`std::map` 是一种有序关联容器，其内部实现了红黑树结构。为了快速定位键值对中的某些特定位置，提供了两个重要的成员函数：`lower_bound` 和 `upper_bound`[^1]。 - **`lower_bound(key)`**: 返回一个迭代器，指向第一个不小于给定键值的元素。如果没有这样的元素，则返回 `end()`。 - **`upper_bound(key)`**: 返回一个迭代器，指向第一个大于给定键值的元素。如果没有这样的元素，则返回 `end()`。 这两个函数的时间复杂度均为 \(O(\log n)\)，因为它们基于二分查找算法工作[^2]。 --- #### 示例代码展示 下面是一段完整的代码示例，演示了如何使用 `lower_bound` 和 `upper_bound`： ```cpp #include <iostream> #include <map> int main() { std::map<int, char> myMap = {{1, 'a'}, {3, 'b'}, {5, 'c'}, {7, 'd'}, {9, 'e'}}; // 使用 lower_bound 找到第一个 >= 4 的键 auto lbIt = myMap.lower_bound(4); if (lbIt != myMap.end()) { std::cout << "Lower bound of 4: (" << lbIt->first << ", " << lbIt->second << ")\n"; } else { std::cout << "No key found greater than or equal to 4.\n"; } // 使用 upper_bound 找到第一个 > 6 的键 auto ubIt = myMap.upper_bound(6); if (ubIt != myMap.end()) { std::cout << "Upper bound of 6: (" << ubIt->first << ", " << ubIt->second << ")\n"; } else { std::cout << "No key found greater than 6.\n"; } return 0; } ``` 运行结果如下： ``` Lower bound of 4: (5, c) Upper bound of 6: (7, d) ``` --- #### 二分查找的工作原理 `lower_bound` 和 `upper_bound` 都采用了二分查找的思想来加速搜索过程。以下是其实现的核心逻辑： 1. 初始时设定左指针 `left` 指向起始位置，右指针 `right` 指向结束位置前一位。 2. 计算中间索引 `mid = left + (right - left) / 2`，避免溢出。 3. 将目标值与当前中间位置的关键字进行比较： - 若关键字小于目标值，则更新 `left = mid + 1`； - 否则，更新 `right = mid`。 4. 循环直到 `left == right`，此时得到的结果即为目标位置。 由于 `std::map` 内部已经按照键值排序，因此可以直接应用上述二分查找策略[^4]。 --- #### 自定义比较准则的应用 当需要处理复杂的键值类型或自定义排序规则时，可以通过传递额外的比较函数实现定制化的行为。例如： ```cpp #include <iostream> #include <vector> #include <algorithm> struct CustomComparator { bool operator()(const int& lhs, const int& rhs) const { return lhs > rhs; // 降序排列 } }; int main() { std::vector<int> vec = {5, 3, 8, 1, 4}; std::sort(vec.begin(), vec.end(), CustomComparator()); auto it = std::lower_bound(vec.begin(), vec.end(), 4, CustomComparator()); if (it != vec.end()) { std::cout << "Custom Lower Bound: " << *it << "\n"; // 输出 4 } return 0; } ``` 在此例子中，我们通过重载运算符的方式创建了一个降序比较器，并将其应用于 `lower_bound` 函数中[^5]。 --- #### 插入新元素的影响 值得注意的是，每当有新的键值被插入到 `std::map` 中时，原有的顺序会被自动维护，不会破坏后续调用 `lower_bound` 或 `upper_bound` 的正确性[^3]。 ---