lower_bound和upper_bound的写法

<think>首先，用户的问题是：“我想查找lower_bound和upper_bound的实现方法或使用示例 请问C++ lower_bound 和 upper_bound 的用法和实现”。系统指令要求我使用中文回答，结构清晰，逐步解决问题，并保证回答真实可靠。 系统指令还指定了格式： - 行内数学表达式使用$...$，例如 $x^2$。 - 独立公式使用$$...$$并单独成段。 - LaTeX语法正确。 - 生成相关问题。 - 在引用的段落末尾添加引用标识，如[^1]。 参考的站内引用： - 引用[1]：提到set和map有自己的lower_bound和upper_bound，效率高于STL中的通用版本。 - 引用[2]：给出了lower_bound的实现代码。 - 引用[3]：展示了std::lower_bound和std::upper_bound在map中的使用示例。 - 引用[4]：解释了lower_bound和upper_bound的常见用法，包括参数和返回值。 我需要基于这些引用构建回答。用户要求的是lower_bound和upper_bound的用法和实现方法。 结构化回答： 1. **引言**：简要介绍lower_bound和upper_bound是什么。 2. **用法**：解释如何在C++中使用它们，包括在vector和map中的示例。 3. **实现方法**：提供或描述算法的实现。 4. **示例**：给出代码示例。 5. **相关问题**：生成相关问题。 确保回答真实可靠：基于标准C++库的知识，引用提供的资料。 关键点： - lower_bound：返回第一个大于或等于给定值的元素的迭代器。 - upper_bound：返回第一个大于给定值的元素的迭代器。 - 在有序容器中使用，如vector、set、map。 从引用[2]，有lower_bound的实现代码： ```c int lower_bound(int *array, int size, int val) { int first = 0; int len = size; while (len > 0) { int half = len >> 1; int middle = first + half; if (array[middle] < val) { first = middle + 1; len = len - half - 1; } else { len = half; } } return first; } ``` 这是一个二分查找的实现。 从引用[3]，有map中的使用示例： ```c++ #include <iostream> #include <map> int main() { std::map<char, int> mymap; std::map<char, int>::iterator itlow, itup; mymap['a'] = 20; mymap['b'] = 40; mymap['c'] = 60; mymap['d'] = 80; mymap['e'] = 100; itlow = mymap.lower_bound('b'); // points to 'b' itup = mymap.upper_bound('d'); // points to 'e' mymap.erase(itlow, itup); // erases from 'b' to 'd' for (auto it = mymap.begin(); it != mymap.end(); ++it) std::cout << it->first << " => " << it->second << '\n'; return 0; } ``` 输出应为a和e。 从引用[4]，lower_bound的用法描述：在数组中找到第一个大于或等于num的元素，返回地址或下标。 生成相关问题： 1. lower_bound和upper_bound在无序容器中能用吗？ 2. 如何用lower_bound实现二分查找？ 3. 在自定义比较函数时如何使用它们？ 回答结构： - 先解释概念。 - 提供用法。 - 展示实现。 - 给出示例。 - 添加相关问题。 确保使用中文。</think>### C++ `lower_bound` 和 `upper_bound` 的用法与实现 在 C++ 标准库中，`lower_bound` 和 `upper_bound` 是用于有序序列（如数组、`vector`、`set`、`map`）的高效二分查找算法。它们基于二分查找原理，时间复杂度为 $O(\log n)$。下面我将从用法、实现方法和示例三个方面详细解释，确保内容真实可靠（基于 C++ 标准和常见实践）。 --- #### 1. **核心概念和用法** - **`lower_bound`**：返回序列中第一个**大于或等于**给定值的元素的迭代器（或下标）。如果值不存在，返回指向序列末尾的迭代器。 数学描述：在有序序列 $[begin, end)$ 中，找到最小索引 $i$ 满足 $a_i \geq val$。 - **`upper_bound`**：返回序列中第一个**大于**给定值的元素的迭代器（或下标）。如果值不存在，返回序列末尾。 数学描述：在有序序列 $[begin, end)$ 中，找到最小索引 $i$ 满足 $a_i > val$。 - **适用容器**：需有序序列，如 `std::vector`, `std::set`, `std::map`。对于关联容器（如 `set` 和 `map`），优先使用其成员函数版本（`set.lower_bound(val)`），效率更高，因为直接利用内部树结构[^1]。 - **参数格式**： ```cpp // 通用版本（适用于 vector 等） iterator lower_bound(iterator begin, iterator end, const T& val); iterator upper_bound(iterator begin, iterator end, const T& val); // 成员函数版本（适用于 set/map） set.lower_bound(val); // 返回 set 的迭代器 map.lower_bound(key); // 返回 map 的迭代器 ``` - **返回值**：迭代器或下标。通过 `std::distance(begin, iter)` 可获取下标。 --- #### 2. **实现方法（基于二分查找）** 这两个函数的底层实现是二分查找。以下是 `lower_bound` 的经典实现（基于引用[2]的代码，优化为 C++ 风格）： ```cpp // lower_bound 实现：在有序数组 array 中查找 val template <typename T> int lower_bound(T* array, int size, T val) { int first = 0; int len = size; while (len > 0) { int half = len >> 1; // 等价于 len / 2 int middle = first + half; if (array[middle] < val) { first = middle + 1; len = len - half - 1; // 调整剩余长度 } else { len = half; // 调整剩余长度 } } return first; // 返回下标 } ``` - **算法原理**： - 初始化 `first=0` 和 `len=size`，表示搜索区间 $[first, first+len)$。 - 循环中，计算中点 `middle`。如果中点值小于 `val`，则搜索右半区间；否则搜索左半区间。 - 最终返回 `first`，即第一个 $\geq val$ 的元素下标。 - **`upper_bound` 实现**：类似 `lower_bound`，但条件改为 `if (array[middle] <= val)`，确保找到第一个 $> val$ 的元素。 - **数学保证**：二分查找确保时间复杂度为 $O(\log n)$，空间复杂度 $O(1)$。 --- #### 3. **使用示例** 下面通过 `vector` 和 `map` 的示例展示具体用法（基于引用[3]和引用[4]）。 **示例 1：在 vector 中查找下标** ```cpp #include <iostream> #include <vector> #include <algorithm> // 需要包含此头文件 int main() { std::vector<int> vec = {10, 20, 30, 30, 40, 50}; int val = 30; // lower_bound：返回第一个 >=30 的元素迭代器 auto low = std::lower_bound(vec.begin(), vec.end(), val); int low_idx = std::distance(vec.begin(), low); // 下标计算 std::cout << "lower_bound 下标: " << low_idx << " (值: " << *low << ")\n"; // 输出: 下标: 2 (值: 30) // upper_bound：返回第一个 >30 的元素迭代器 auto up = std::upper_bound(vec.begin(), vec.end(), val); int up_idx = std::distance(vec.begin(), up); std::cout << "upper_bound 下标: " << up_idx << " (值: " << *up << ")\n"; // 输出: 下标: 4 (值: 40) // 应用：删除所有值为 30 的元素 vec.erase(std::lower_bound(vec.begin(), vec.end(), 30), std::upper_bound(vec.begin(), vec.end(), 30)); for (int x : vec) std::cout << x << " "; // 输出: 10 20 40 50 return 0; } ``` **示例 2：在 map 中使用成员函数（高效版）** ```cpp #include <iostream> #include <map> int main() { std::map<char, int> mymap; mymap['a'] = 20; mymap['b'] = 40; mymap['c'] = 60; mymap['d'] = 80; mymap['e'] = 100; // 使用 map 的成员函数 lower_bound/upper_bound auto itlow = mymap.lower_bound('b'); // 指向 'b' (键值 >= 'b') auto itup = mymap.upper_bound('d'); // 指向 'e' (键值 > 'd') // 删除区间 [itlow, itup)（即 'b' 到 'd'） mymap.erase(itlow, itup); // 输出剩余元素 for (auto it = mymap.begin(); it != mymap.end(); ++it) std::cout << it->first << " => " << it->second << '\n'; // 输出: a => 20, e => 100 return 0; } ``` - **关键点**： - 在 `map` 中，`lower_bound('b')` 返回指向键 `'b'` 的迭代器，`upper_bound('d')` 返回指向 `'e'` 的迭代器（因为 `'e'` 是第一个大于 `'d'` 的键）[^3]。 - 成员函数版本比通用 `std::lower_bound` 更快，因为它直接利用红黑树结构[^1]。 --- #### 注意事项 - **序列必须有序**：使用前确保容器已排序，否则行为未定义。 - **自定义比较**：支持传入比较函数，如 `std::lower_bound(vec.begin(), vec.end(), val, custom_comp)`。 - **性能**：二分查找确保高效，但频繁插入/删除时，优先选择 `set/map`。 ---