二分查找与二分答案模板
二分查找
首先是二分查找：
二分查找，顾名思义，就是不断折半查找。每次取中间的数跟目标比，如果中间的数小了，说明目标在右边，就把左边缩到mid+1；如果中间的数大了，说明目标在左边，就把右边缩到mid-1。这样每次都能扔掉一半的数据，很快就能找到。
以下是普通的写法：
int ef(int x) { int l=1,r=n; while(l<=r) { int mid=(l+r)/2; if(a[mid]==x) return mid; if(a[mid]<x) l=mid+1; else r=mid-1; } return -1; }这样写就是最常见的闭区间二分查找。l和r分别表示当前查找范围的左右边界，一开始l=1（第一个位置），r=n（最后一个位置）。每次取中间位置mid，然后比较a[mid]和x：
如果相等，说明找到了，直接返回mid
如果a[mid] < x，说明x在右边，把l移到mid+1
如果a[mid] > x，说明x在左边，把r移到mid-1
循环条件是l <= r，意思是只要区间里还有数就继续找。当l > r的时候，说明区间空了，x不在数组里，返回-1。
举个例子
数组：1 2 3 4 5 6 7 8 9 10，找5
开始：l=1, r=10
mid=5 → a[5]=5，找到了，返回5
找11：
l=1, r=10
mid=5 → a[5]=5 < 11 → l=6
mid=8 → a[8]=8 < 11 → l=9
mid=9 → a[9]=9 < 11 → l=10
mid=10 → a[10]=10 < 11 → l=11
现在l=11, r=10，l > r，循环结束，返回-1
找0：
l=1, r=10
mid=5 → a[5]=5 > 0 → r=4
mid=2 → a[2]=2 > 0 → r=1
mid=1 → a[1]=1 > 0 → r=0
l=1, r=0，l > r，结束，返回-1
为什么mid+1和mid-1
因为mid已经比较过了，确定不是x，所以下一次查找的范围可以把它排除掉。左边就从mid+1开始，右边就到mid-1为止。
这种写法的几个注意点
循环条件是l <= r，不是l < r。如果写成l < r，当l和r相等的时候循环就退出了，但l和r相等的时候那