史上最傻瓜二分推导!!!
题:假设通过二分查找最后一个是b
的数的索引。
例如:1 2 2 3 3 4
,查找3
,返回4
(最后一个3的索引是4)
推导:
假设二分规则为:(左边界+有边界)// 2
通过三个例子来说明涉及的三种情况:
1.比目标数小
1 | 2 | 2 | 3 | 3 | 4 |
---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 |
在上面数组中查找b=3
先二分 (0+5)/2=2 ,此时对应的V[2]值为2
因为2<b,在索引2和2之前的我都不需要了,因此更新为:3~5
3 | 3 | 4 |
---|---|---|
3 | 4 | 5 |
2.比目标数大
1 | 2 | 4 | 4 | 4 | 4 |
---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 |
在上面数组中查找b=2
先二分 (0+5)// 2=2 ,此时对应的V[2]值为4
因为4>b,在索引2和2之后的我都不需要了,因此更新为:0~1
1 | 2 |
---|---|
0 | 1 |
3.和目标数相等
1 | 2 | 3 | 3 | 3 | 4 |
---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 |
在上面数组中查找b=3
先二分 (0+5)// 2=2 ,此时对应的V[2]值为3
因为3=b,在索引2之前的我都不需要了,但是我要保留索引2,因为无法确定它是否是需要被丢弃的索引,因此更新为:2~5
3 | 3 | 3 | 4 |
---|---|---|---|
2 | 3 | 4 | 5 |
总结:
-
比目标数小 mid+1~r
-
比目标数大 l~mid-1
-
和目标数相等 mid~r
优化总结:
-
比目标数小或等于目标数 mid~r
-
比目标数大 l~mid-1
-
这也是为什么二分在求上界的时候是l~mid-1 、mid~r去二分的原因了。
- 同理,求下界时也可以用如上方法推导
改进:
处理二分时最头疼的是死循环问题,可以用二元素的特殊例子判断是否会出现死循环
1 | 2 |
---|---|
0 | 1 |
此时要找元素2,现在的索引范围是(0,1)
步骤如下:
- 先二分(0+1)//2=0
- V[0]是1<2,更新后依然是
(0,1)
因此本处理二分的办法会发生死循环,解决办法:二分规则改为(l+r+1)//2
即可
区别和原理:
两者区别在于左二分和右二分的区别:
左二分(l+r)// 2
:
当二分为(l~mid 、mid+1~r)时,可以考虑左二分。左二分才能正好切分为两个
中间值(mid) | mid+1 | ||
---|---|---|---|
右二分(l+r+1)//2
:
当二分为(l~mid-1 、mid~r)时,可以考虑右二分。右二分才能正好切分为两个
mid-1 | 中间值(mid) | ||
---|---|---|---|
当个数为奇数时,左右二分结果一致:
中间值 | ||||
---|---|---|---|---|
巧记:
知道你们记不住,所以我也写一个巧计方法hh:
众所周知,男左女右
当l=mid时候,就代表选中男方,男生是1,所以二分是l+r+1
当r=mid时候,就代表选中女方,女生是0,所以二分是l+r+0
核心代码
int LBS(int l,int r)//下界
{
while (l<r)
{
int mid = (l+r) >> 1;//女右
if(V[mid]<b)
l=mid+1;
if(V[mid]>=b)
r=mid;//我是女生
}
if(V[r]==b) return r;
else return -1;
}
int HBS(int l,int r)//上界
{
while (l<r)
{
int mid = (l+r+1) >> 1;//男左
if(V[mid]<=b)
l=mid;
if(V[mid]>b)
r=mid-1;//我是男生
}
if(V[r]==b) return r;
else return -1;
}
创新思路:
以下是我个人的创新思路:
综述上面的推导,如何二分区间,是l~mid-1 、mid~r 还是 l~mid 、mid+1~r。关键取决于目标数相等这种情况罢了
那我为什么要把这个相等情况转化成一般情况呢?我挑出来另外考虑不就好了!
我把刚刚的分类讨论再拿出来:
-
比目标数小 mid+1~r
-
比目标数大 l~mid-1
-
和目标数相等 mid~r
现在咱们不需要把它合并,进一步细化
- 比目标数小 mid+1~r
- 比目标数大 l~mid-1
- 和目标数相等
- 如果后面一个数和当前数不相等,说明是上界限了
- 如果后面一个数和当前数相等,那我直接mid+1~r了
这样我的划分依据就是mid+1~ r和 l ~mid-1 ,不会出现死循环问题,因为区间一直会缩小
求下界也可以用这种办法思考
代码如下:
int HBS(int l,int r,int b)
{
if(l==r && V[l]!=b)
return -1;
if(l==r && V[l]==b)
return l;
int mid = (l+r)>>1;
int value = V[mid];
if(value==b && value!=V[mid+1])
return mid;//说明是上界限了
if((value==b && value==V[mid+1])||(value<b))
return HBS(mid+1,r,b);
if(value>b)
return HBS(l,mid-1,b);
}
int LBS(int l,int r,int b)
{
if(l==r && V[l]!=b)
return -1;
if(l==r && V[l]==b)
return l;
int mid = (l+r)>>1 ;
int value = V[mid];
if(value==b && value!=V[mid-1])
return mid;//说明是下届限了
if((value==b && value==V[mid-1])||(value>b))
return LBS(l,mid-1,b);
if(value<b)
return LBS(mid+1,r,b);
}
代码看起来多,但是思考起来更加简单了
鄙人对二分的一些研究,欢迎大佬指点不足之处