如何对std::vector执行二分搜索并返回RandomAccessIterator？

核心结论 #

你完全不需要重新实现std::lower_bound——标准库的std::lower_bound针对std::vector的迭代器（天然是RandomAccessIterator），本身就是**O(log₂N)**的二分查找实现，返回的迭代器也直接是RandomAccessIterator类型，完全符合你的需求。

具体步骤 #

1. 用std::lower_bound搜索第一个vector
   直接调用标准库函数，它会自动利用std::vector迭代器的随机访问特性做二分查找，时间复杂度O(log₂N)：

   #include <vector>
   #include <algorithm>
   
   std::vector<int> vec1 = {1, 3, 5, 7, 9};
   int target = 6;
   // 返回的it1是RandomAccessIterator类型
   auto it1 = std::lower_bound(vec1.begin(), vec1.end(), target);
   

2. O(1)时间获取索引
   对于RandomAccessIterator，直接用迭代器减法就能在常数时间内得到索引，完全不需要线性时间的std::distance（当然std::distance对随机访问迭代器也是O(1)，但减法更直观）：

   size_t match_idx = it1 - vec1.begin();
   

3. 定位第二个vector的子范围
   利用得到的索引，通过迭代器加法直接定位第二个更大vector的子范围，同样是O(1)操作：

   std::vector<int> vec2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   // 例如子范围从对应索引位置开始到末尾
   auto sub_range_begin = vec2.begin() + match_idx;
   auto sub_range_end = vec2.end();
   // 此时[sub_range_begin, sub_range_end]就是你需要的子范围
   

关键说明 #

• 为什么std::lower_bound是O(log₂N)？标准库规定，当输入迭代器是RandomAccessIterator时，std::lower_bound必须使用二分查找实现，时间复杂度为对数级；只有当迭代器是ForwardIterator（比如std::list的迭代器）时，才会退化为线性遍历。
• 迭代器减法/加法的性能：std::vector的迭代器本质是指针（或类指针），算术运算都是直接的地址计算，完全是O(1)，没有任何性能损耗。

内容的提问来源于stack exchange，提问作者user1804394