0.前言

二分法并不简单，或者说“思路简单，细节爆炸”，举例来说，你可能已经看过很多题解，那么可能会看到下面几种写法

mid=(left+right)/2    mid=(left+right)>>1    mid=left+(left+right)/2    mid=left+((left+right)>>1)     mid = (left+right)/2 +1    mid = (left+right+1)/2

//结束条件写法  while(left<right)    while(left<=right)    while(left+1<left)

//边界值的取法  ...  if( )     left=mid;  else     right=mid;  ...    ...  if( )     left=mid+1;  else     right=mid;  ...    ...  if( )     left=mid+1;  else     right=mid-1;  ...    ...  if( )     left=mid;  else     right=mid-1;  ...

第一次看完之后，我的心情:

本来以为很简单，仔细搜索一下，简直要爆炸了，在网上和书上找了很多资料，终于整理出来了。

实际上，二分搜索的题型可以简单归结成几类吧

第一类：二分查找，寻找中间值

第二类：左端点值

第三类：右端点值

1.中间值选取问题

在二分法求解过程中，我们经常使用

mid=(left+right)/2

但是很多地方也有这样的写法

mid=left+(left+right)/2
或
mid=left+((left+right)>>1)    //使用右移最好加括号，

问题1：负数问题

#include<cstdio>  int main() {    	int left,right,mid1,mid2,mid3,mid4;    	scanf("%d%d",&left,&right);    	mid1 = (left+right)/2;    	mid2 = (left+right)>>1;    	mid3 = left+(right-left)/2;    	mid4 = left+((right-left)>>1);  	  	printf("%d,%d,%d,%d",mid1,mid2,mid3,mid4);    	return 0;     }        //输入是 99 100  输出结果是99,99,99,99    //输入是 100 99  输出结果是99,99,100,99    //输入是 -99 -100 输出结果是-99,-100,-99,-100    //输入是 -100 -99 输出结果是-99,-100,-100,-100

int类型的取整是向0取整,即使被取整的数绝对值变小

而右移是向下取整,即使被取整的数值变小

所以对于正数时两者相同,而到了负数则变大

问题2：溢出问题

#include<cstdio>  int main() {    	int left,right,mid1,mid2,mid3,mid4;    	scanf("%d%d",&left,&right);    	mid1 = (left+right)/2;    	mid2 = (left+right)>>1;    	mid3 = left+(right-left)/2;    	mid4 = left+((right-left)>>1);  	  	printf("%d,%d,%d,%d",mid1,mid2,mid3,mid4);    	return 0;     }        //输入是 1999999998 1999999998    // 输出结果分别是    // -147483650    // -147483650    // 1999999998    // 1999999998

问题3：起点问题

对于不同的数组，有的可能是从i=0 开始读入，有的可能是从i=1 开始读入