By

两个二分函数自定义对于结构体的二分查找，还有官方的自定义比较函数。

lower_bound() 有两种形式。

  • lower_bound (first, last, val); （无自定义比较）
  • lower_bound (first, last, val, Compare comp); （自定义比较）

在有序的前提下，lower_bound 返回指向第一个值不小于 val 的位置，也就是返回第一个大于等于 val 的值的位置。（通过二分查找，$O(log_2n)$ 的复杂度）。

如果没有大于等于 val 的元素，会指向末尾元素的下一个。

无自定义比较使用

  • STL的使用方式
vector<int> v={2,3,4,5,6};
vector<int>::iterator it;
it=lower_bound(v.begin(),v.end(),3);
cout<<(*it)<<endl;//(*it)为对应的值
cout<<v[it-v.begin()];//it-v.begin()为第几个元素（从0开始）
//如果元素全部小于 val ,则 it=v.end()
  • 数组的使用方式
int a[100],n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int x=lower_bound(a+1,a+n+1,3)-a;//不论从0开始，还是从1开始，都只-数组名
cout<<a[x]<<endl;//x为对应下标
//如果元素全部小于 val ,则 x=n+1
  • 自定义查找使用
  • 返回第一个false的元素 , val是自定义函数的第二个参数
  • 前提是有序（从左往右==从满足cmp到不满足cmp的单调性），不然会按照折半来查找，可能得到的不是第一个满足条件的
bool cmp(int e,int val){
	return e>=val;
}
int main(){
	int a[100],n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int x=lower_bound(a+1,a+n+1,3,cmp)-a;
    //找到的是第一个小于3的元素
	cout<<x<<endl;
	return 0;
}
  • 官方的比较函数
lower_bound( begin , end , val , less<type>() )
加入了less<type>()比较函数：适用于从小到大排序的有序序列，
查找第一个大于等于 val 的数字
lower_bound( begin , end , val , greater<type>() )
加入了greater<type>()比较函数：适用于从小到大排序的有序序列，
查找第一个小于等于 val 的数字
  • 结构体二分查找
struct Student{
	int _id;  //学号
	int _num; //排名
 
	Student(int id, int num)
		:_id(id)
		, _num(num)
	{}
}Stu;
struct CompareV
{
	bool operator() (const Stu& s1,  const Stu& s2)//  排名升序
	{	
		return s1._num < s2._num;
	}
};
int main()
{
	vector<Stu> vS = { { 101, 34 }, { 103, 39 }, { 102, 35 } };
	//CompareV()排完序后是这个丫子
	//101 34
	//102 35
    //103 39
	auto iter = lower_bound(vS.begin(), vS.end(), Stu(200,33), CompareV());
	cout << iter - vS.begin() << endl; //我们就找到了按仿函数排序(找排名比33大的位置 就是0）
}
  lower_bound upper_bound
无比较函数 返回第一个 >=x 的元素 返回第一个 >x 的元素
有比较函数 返回 第一个 false 的元素 返回 第一个 true 的元素