【二分与分治】中间值、边界值、循环条件、模块写法(1)
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,-100int类型的取整是向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 开始读入
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
