关于STL中的二分(lower_boundupper_bound)

lower_boundupper_bound这两个函数是为了支持随机访问随机访问迭代器而设计的。1.lower_bound模版结构// 查找第一个【大于或等于】value 的位置templateclassForwardIt,classTForwardItlower_bound(ForwardIt first,ForwardIt last,constTvalue);first / last: 搜索范围必须是有序序列。value: 要查找的目标值。返回值: 返回一个指向该元素的迭代器如果找不到则返回 last。操作示例vectorintv{1,2,4,4,4,6,7};// 查找第一个 4 的位置autoit_lowstd::lower_bound(v.begin(),v.end(),4);// 指向第一个 4 的下标下标 22.upper_bound模版结构// 查找第一个【严格大于】value 的位置templateclassForwardIt,classTForwardItupper_bound(ForwardIt first,ForwardIt last,constTvalue);first / last: 搜索范围必须是有序序列。value: 要查找的目标值。返回值: 返回一个指向该元素的迭代器如果找不到则返回 last。操作示例vectorintv{1,2,4,4,4,6,7};// 查找第一个 4 的位置autoit_upstd::upper_bound(v.begin(),v.end(),4);// 指向数字 6 的下标下标 53. 关联容器的成员函数特别注意对于有序关联容器必须使用其自带的成员函数而非全局算法。核心差异虽然全局的std::lower_bound也能处理set或map但因为关联容器的迭代器不支持随机访问全局算法会退化为线性查找O(N)O(N)O(N)。而成员函数版本利用红黑树的特性能保证对数查找O(log⁡N)O(\log N)O(logN)。常用容器接口// 以 std::set 为例iteratorlower_bound(constKeykey);iteratorupper_bound(constKeykey);// 以 std::map 为例仅针对 Key 进行查找iteratorlower_bound(constKeykey);iteratorupper_bound(constKeykey);操作示例std::setsetints{10,20,30,40,50};// 查找第一个 25 的元素autoit_lows.lower_bound(25);// 指向 30// 查找第一个 30 的元素autoit_ups.upper_bound(30);// 指向 40操作示例std::map在 map 中这两个函数只检查 Key。std::mapint,stringm{{1,apple},{3,banana},{5,cherry}};autoitm.lower_bound(2);// 返回迭代器指向 {3, banana}因为 3 是第一个 2 的键4. 进阶equal_range如果你需要同时获取lower_bound和upper_bound例如在multiset中找出所有等于某个值的区间可以使用equal_range。模版结构// 返回一个 pair包含 [lower_bound, upper_bound)std::pairiterator,iteratorequal_range(constKeykey);实际应用std::multisetintms{1,2,2,2,3};autorangems.equal_range(2);// range.first - 指向第一个 2// range.second - 指向数字 3 (第一个严格大于 2 的位置)// 距离即为元素个数autocountstd::distance(range.first,range.second);// 结果为 3总结如何选择容器类型推荐函数时间复杂度vector / array / dequestd::lower_boundO(log⁡N)O(\log N)O(logN)set / map / multiset /multimapcontainer.lower_bound()O(log⁡N)O(\log N)O(logN)liststd::lower_boundO(N)O(N)O(N)(不推荐对 list 频繁二分)unordered_set/unordered_map不支持(无序容器没有边界概念)N/A