C++ lower_bound函数返回错误迭代器，查找7和4均返回索引2

问题原因 #

lower_bound 是基于二分查找实现的STL算法，C++标准明确规定：默认使用小于比较的场景下，lower_bound 处理的迭代器范围必须是升序有序的。
你当前测试用的vector构造完成后序列为 [1, 3, 7, 4, 9]，7之后插入了更小的4，整个序列不满足升序要求，因此lower_bound的执行结果不符合预期属于正常情况，这是未定义行为的典型表现，在不同编译环境下甚至可能得到完全不同的输出。

修复方案 #

调用lower_bound前先对序列做升序排序即可得到正确结果，修改后的代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(7);
    v.push_back(4);
    v.push_back(9);
    // 新增排序步骤，保证序列升序
    sort(v.begin(), v.end());
    // 排序后序列为 [1,3,4,7,9]
    cout<<"lower bound of 7 : "<<lower_bound(v.begin(),v.end(),7)-v.begin()<<endl;
    cout<<"lower bound of 4 : "<<lower_bound(v.begin(),v.end(),4)-v.begin()<<endl;
}

修改后输出结果为：

lower bound of 7 : 3
lower bound of 4 : 2

如果业务不允许修改原序列顺序，不可直接使用lower_bound，可选择线性遍历查找，或者单独维护一份有序副本用于查找操作。

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