c++中set二分搜索

在 C++ 中，`set` 是一种基于红黑树实现的关联容器，其内部元素默认按照升序排列。由于 `set` 的有序性，可以在其中高效地使用二分查找算法，时间复杂度为 $ O(\log n) $。C++ 标准库提供了 `lower_bound` 和 `upper_bound` 成员函数来支持这种操作。 ### 使用方法 #### 1. `lower_bound` 该函数返回一个迭代器，指向第一个不小于给定值的元素。如果找不到这样的元素，则返回 `set.end()`。 ```cpp #include <iostream> #include <set> int main() { std::set<int> s = {1, 3, 5, 7, 9}; int target = 6; auto it = s.lower_bound(target); if (it != s.end()) { std::cout << "Lower bound of " << target << " is " << *it << std::endl; // 输出: Lower bound of 6 is 7 } else { std::cout << "No lower bound found for " << target << std::endl; } return 0; } ``` #### 2. `upper_bound` 该函数返回一个迭代器，指向第一个大于给定值的元素。如果找不到这样的元素，则返回 `set.end()`。 ```cpp #include <iostream> #include <set> int main() { std::set<int> s = {1, 3, 5, 7, 9}; int target = 6; auto it = s.upper_bound(target); if (it != s.end()) { std::cout << "Upper bound of " << target << " is " << *it << std::endl; // 输出: Upper bound of 6 is 7 } else { std::cout << "No upper bound found for " << target << std::endl; } return 0; } ``` #### 3. 查找特定值 通过 `find` 函数可以直接查找指定值的元素，若找到则返回对应的迭代器，否则返回 `set.end()`。 ```cpp #include <iostream> #include <set> int main() { std::set<int> s = {1, 3, 5, 7, 9}; int target = 5; auto it = s.find(target); if (it != s.end()) { std::cout << "Found element: " << *it << std::endl; // 输出: Found element: 5 } else { std::cout << "Element not found" << std::endl; } return 0; } ``` ### 原理 `set` 容器内部采用红黑树结构进行实现，确保了所有插入、删除和查找操作的时间复杂度均为 $ O(\log n) $。由于红黑树是一种自平衡的二叉搜索树，因此可以高效地支持二分查找操作。`lower_bound` 和 `upper_bound` 实际上利用了红黑树的特性，在对数时间内完成查找任务[^3]。 ### 注意事项 - `set` 中的元素是唯一的且按升序排列，这保证了查找时的有序性，使得二分查找得以高效进行。 - 如果需要支持重复元素并进行类似的查找操作，可以使用 `multiset`，其用法与 `set` 类似，但允许存储重复的元素[^3]。 ###