如何高效查找有序std::vector<int>中首个大于a且小于b的元素索引

因为你的std::vector<int>是有序的，完全可以用二分查找替代线性遍历，时间复杂度从O(n)降到O(logn)，数据量越大效率提升越显著。

优化后的代码 #

#include <iostream>
#include <vector>
#include <algorithm> // 必须包含该头文件以使用二分查找算法

int main() {
    const int a = 2, b = 4; // a始终小于b
    const std::vector<int> vec {1, 2, 3, 4, 5};

    int ans_index = -1;
    // 用upper_bound快速定位第一个大于a的元素迭代器
    auto target_it = std::upper_bound(vec.begin(), vec.end(), a);
    
    // 检查迭代器是否有效，且元素值小于b
    if (target_it != vec.end() && *target_it < b) {
        ans_index = std::distance(vec.begin(), target_it);
    }

    std::cout << "符合条件的第一个元素索引：" << ans_index << std::endl;
    // 可选：输出对应元素值
    if (ans_index != -1) {
        std::cout << "对应元素值：" << vec[ans_index] << std::endl;
    }
    return 0;
}

代码说明 #

• std::upper_bound：利用二分查找在升序序列中快速找到第一个大于a的元素，这一步是O(logn)复杂度
• 后续只需检查该元素是否小于b：如果满足，用std::distance计算其索引；如果不满足或迭代器指向末尾，说明没有符合条件的元素，返回-1

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