二分查找与二分答案模板

二分查找首先是二分查找：二分查找，顾名思义，就是不断折半查找。每次取中间的数跟目标比，如果中间的数小了，说明目标在右边，就把左边缩到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=10mid=5 → a[5]=5，找到了，返回5找11：l=1, r=10mid=5 → a[5]=5 11 → l=6mid=8 → a[8]=8 11 → l=9mid=9 → a[9]=9 11 → l=10mid=10 → a[10]=10 11 → l=11现在l=11, r=10，l r，循环结束，返回-1找0：l=1, r=10mid=5 → a[5]=5 0 → r=4mid=2 → a[2]=2 0 → r=1mid=1 → a[1]=1 0 → r=0l=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相等的时候那