C++中的二分_c++二分

二分是算法中比较基础简单的，但是边界值问题是二分问题比较头疼的

如果处理不好很容易会越界，或者死循环。

二分查找一个确定值（不考虑相同值的左右边界）

本二分查找采用搜索左闭右开的区间数组，所以 [l,r) = [l,r-1];

如果从下标1开始记录第一个数，那查找区间 [1,n+1] r=n（实际长度）+1 

或者[1,num.size]，size包括了arr[0]的个数了 num.size=n+1

如果从下标0开始记录第一个数，那查找区间为 [0,n] 因为 arr[0]也记录也一个数，arr[n]没有记录

或者[0,num.size] 

	int l=1,r=num.size();
	int mid;
    int flag=1;
	while(l<r){
		 mid=(l+r)/2;
		if(num[mid] == x)
		{
            flag=0;
			break;
		}
		else if(num[mid] > x)
		{
			r=mid;
		}
		else if(num[mid] < x)
		{
			l=mid+1;
		}
	}
    if(flag)
    {
        cout<<"0";
    }
    else
    {
        cout<<num[mid];
    }

或者

int bina(int l ,int r,int x)
{
	int mid;
	while(l<r){
		mid=(l+r)/2;
		if(num[mid] == x)
		{
			return mid;
		}
		else if(num[mid] > x)
		{
			r=mid;
		}
		else if(num[mid] < x)
		{
			l=mid+1;
		}
	}
    retuen -1;
}

二分查找相同元素的边界值（左边界或者右边界）

如vector<int> num = {0,2,4,7,7,7,8,12,15,17,19,20,23,25};

需要查找最左边或者右边的7

查找相同元素的左边界值

	int l=0,r=num.size();
    int mid;
	while(l<r){
		mid=(l+r)/2;
		//cout<<l<<" "<<r<<" "<<mid<<endl;
		if(num[mid] == x)
		{
			r=mid;//如果找到相等值，向左收缩继续，将mid变成右边界开区间
		}
		else if(num[mid] > x)
		{
			r=mid;
		}
		else if(num[mid] < x)
		{
			l=mid+1;
		}
	}
	cout<<l<<" "<<num[l]<<endl;

查找相同元素的右边界值

		int l=1,r=num.size();
        int mid;
		while(l<r){
			 mid=(l+r)/2;
			 //cout<<l<<" "<<r<<" "<<mid<<endl;
			 cout<<l<<" "<<r<<" "<<mid<<endl;
			if(num[mid] == x)
			{
				l=mid+1;//如果找到相等值，向右收缩继续，右边界值不变，左边界值（l+1，r]
			}
			else if(num[mid] > x)
			{
				r=mid;
			}
			else if(num[mid] < x)
			{
				l=mid+1;
			}
		}
	    cout<<l-1<<" "<<num[l-1]<<endl;

查找右边界的时候。一定要注意，目标值为l-1，因为r一直大于目标值

如果找不到目标值，就默认返回比 目标值 第一个大的元素

c++<algorithm>中二分算法

lower_bound :

lower_bound(begin,end,目标值) ,从begin到end-1位置，二分查找等于目标值的下标，如果没有找到，就返回第一个比目标值大的元素，获取下标应在减去num，

int k = lower_bound(num,num+k,x) - num

upper_bound:

upper_bound(begin,end,目标值),从begin到end-1位置，二分查找第一个大于目标值的下标

注意：使用vector时，应该用迭代器，

auto it =upper_bound(num.begin(),num.end(),x)-num.begin()

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<int> num = {0,2,4,7,7,7,8,12,15,17,19,20,23,25};
             //      1 2 3 4 5 6  7  8 9  10 11 12 13
int numm[] = {0,2,7,7,7,8,9,10,12,12,15,16};
           // 0 1 2 3 4 5 6  7  8  9 10 11
 
int main()
{
	
	int x;
	cin>>x;
	int i = lower_bound(numm,numm+12,x)-numm;
	cout<<i<<" "<<numm[i]<<endl;
	auto pos=upper_bound(num.begin(),num.end(),x)-num.begin();
	cout<<num[pos];
 
}

按从大到小排序返回第一个小于目标值的 下标
 int pos=lower_bound(num,num+n,查找值,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
 iint pos=upper_bound(num,num+n,查找,greater<int>())-num;  //返回数组中第一个小于被查数的值 

二分查找例题

Problem - 1742E - Codeforces