526互联

二分——lower_bound&upper_bound写法

发布时间 2023-12-23 22:36:43作者: fedoralxy

底层实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll lower_bound(vector<ll>& nums,ll x)
{
	ll left=0;
	ll right=nums.size()-1;
	while(left<=right) 
	{
		ll mid=left+(right-left)/2;
		if(x>nums[mid])
			left=mid+1;
		else
			right=mid-1;	
	}
	return left;
}
ll upper_bound(vector<ll>& nums,ll x)
{
	ll left=0;
	ll right=nums.size()-1;
	while(left<=right)
	{
		ll mid=left+(right-left)/2;
		if(x>=nums[mid])
			left=mid+1;
		else
			right=mid-1;	
	}
	return left;
}
int main(){return 0;}

用法

  • lower_bound()

    1. 返回值是第一个大于/等于所要查找的元素地址
    2. 适用于非降序排列
    3. 格式：lower_bound(起始地址,末尾地址,查找元素)

  • upper_bound()

    与 lower_bound() 同理。

示例(lower_bound(),upper_bound()同理）

ll a[]={1,2,3};
cout<<lower_bound(a,a+3,2)-a;

vector<int> v;
v.push_back(1),v.push_back(2),v.push_back(3);
cout<<lower_bound(v.begin(),v.end(),2)-v.begin();