手写实现及基于 STL 实现的二分代码比较

【Find the position of the first element that >=target】

//Find the position of the first element that >=target
int ffir(vector<int>& v,int target) {auto it=lower_bound(v.begin(),v.end(),target);return it-v.begin();
}int ffir(int le,int ri) {while(le<ri) {int mid=le+ri>>1;if(check(mid)) ri=mid;else le=mid+1;}return le;
}

【Find the position of the last element that <=target】

int flas(vector<int>& v,int target) {auto it=upper_bound(v.begin(),v.end(),target);return it-v.begin()-1;
}int flas(int le,int ri) {while(le<ri) {int mid=le+ri+1>>1;if(check(mid)) le=mid;else ri=mid-1;}return ri;
}

 

​【注意事项】
基于 STL 实现的二分代码，比手写实现的二分代码更简洁、更少出错。
（1）核心前提：数组 v 必须升序排列，否则需加自定义比较函数 auto it = lower_bound(v.begin(), v.end(), target, greater<int>());
（2）边界处理：使用前需判断返回值是否在合法下标范围内 (0 ~ v.size()-1);




【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/157910583

​