二分法-浅析

发表于 阅读次数：

二分法

解题步骤

1.确定左右边界的范围，明确应在什么范围内进行查找是例如一个数组长为n，范围应该是[0,n]还是[0,n-1]

2.选择中间元素和什么值进行比较，

3.然后选择是左中位数还是右中位数

1
2
3
4
5
6
7
8
if(对中位数的判断条件)
{
    right=mid-1;
}
else
{
    left=mid;
}

上面这种就是右边界收缩，因为right=mid-1，left=mid那么我们就必须要选择右中位数

1
2
3
4
5
6
7
8
if(对中位数的判断条件)
{
    left=mid+1;
}
else
{
    right=mid;
}

这种则是左边界收缩，我们就必须选择左中位数

4.最后我们考虑是否要进行left 后处理以获得最终结果

注意：

​ 1.mid的取值有3种取法（以左中位数取为例）

​ 1）mid=（left+right）/2 //右中位数mid=（left+right+1）/2

​ 最普通的一种取法，不建议大家用，很有可能会造成int溢出

​ 2）mid=left+（right-left）/2 //右中位数mid=left+（right-left+1）/2

​ 一般用这种做法不会造成溢出，但若数据很大的时候也会造成溢出

​ 3）mid=（left+right）>>1; //右中位数mid=(left+right+1)>>1

​ 推荐用这种写法，这种不会造成溢出