[算法总结] 二分

---

先辈的话说在前头

二分程序虽然简单， 但是如果写之前不考虑好想要查找的是什么， 十有八九会是死循环或者查找错误，就算侥幸写对了也只是运气好而已。

二分难点:

1.范围控制
2.check条件

范围控制

例题:传送门

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式 第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式 共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

输入样例：

6 3

1 2 2 3 3 4

3

4

5
输出样例：
3 4
5 5
-1 -1

因为我们y总给的是从0的模板 但是个人又特别喜欢从1开始,
所以调试之路开始了

首先分析题意:

给定一个单调的数组a,再给定你一个x ,
找找第一个比x小的位置和找第一个比x大的位置(即找x的区间表示),
（堆？ 不不不 堆不是找最近吗？那就不对了emm 还是老老实实二分吧）

分析完之后,好家伙就是走两个二分呗,那我们来吧开始我们的黄金之路！

第一个二分:(找第一个比x小的位置)

int l =1,r=n; 肯定是从头到尾的区间 不用说吧！
while(l<r)	  这里是判断条件以免死循环
{
		int mid =l+r>>1; 二分标记
		if(a[mid]>=x) r= mid; 
		如果当前值比x大或者等于x 那么我们右边的指针就缩小到目前的位置
		else  l = mid+1;
		否则就说明是小了 我们移动左边的指针
		但是问题来了
		我们为什么 l = mid+1呢？
		原因：
		1. l = mid+1 可以防止死循环
		2. 我们找的是第一个比x小的位置 即 x第一次相出现的位置
		所以在条件 a[mid]<x时候 当找到最后一个x的时候
		我们需要对mid+1 才能表示 第一个x的位置
}

第二个二分:(找第一个比x大的位置)

int l = 1,r= n+1 ; 
为什么这里是1 ~ n+1的区间呢？

while(l+1<r)
{

    int mid = l+r>>1; 
 //  cout<<l<<" "<<r<<" "<<mid<<endl;
 上面是调试过 真·调试了好久
 
    if(a[mid]<=x) l=mid; 如果当前的a[mid]<=x那么我们的左指针移动
    else r= mid; 否则也就是a[mid]>x 我们的右指针移动
}

cout<<l-1<<endl;