二分查找

二分查找有两组写法(这里我就写一组了)，每组有2个算法，最后所求的意义也不同

找出第一个>=x的第一个位置

#include<iostream>
using namespace std;
const int N=10010;
int a[N];
int main()
{
	int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=1,r=n;
    int x;
    cin>>x;
    while(l<=r)
    {
    	int mid=l+r>>1;
        if(a[mid]>=x)r=mid-1;
        else l=mid+1;
    }
    cout<<r+1<<endl;
    return 0;
}

在这里,最后一行也可以输出l,从while循环中看条件,如果a[mid]>=x,那么区间一直在左移,也就是说在最后一次判断的时候,r在x的左边位置,而l满足的条件是<x,也就是说l的最终的位置是是停在了x的左边(这个x不仅仅是数组中存在的,也可以是不存在的)

找出<=x的最后一个位置

#include<iostream>
using namespace std;
const int N=110010;
int a[N],n;
int main()
{
	cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=1,r=n;
    while(l<=r)
    {
    	int mid=l+r>>1;
        if(a[mid]<=x)l=mid+1; 
        else r=mid-1;
    }
    cout<<l-1;
    return 0;
}

这里也是同样的道理,最后可以输出l-1,也可以输出r

总结 之所以这样写是因为要避免死循环,因此,我们就仅仅只是改变了原本的mid直接赋值给的区间端点,所以就是直接把原本要输出的东西还原为mid的值就好了