二分查找算法模板(太强了兄die!)

x33g5p2x  于9个月前 转载在 其他  
字(1.2k)|赞(0)|评价(0)|浏览(69)

二分查找算法模板
 
模板1
当将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时,其更新操作是 r = mid 或 l = mid + 1,计算 mid 时不需要加1,即 mid = (l + r)/2。

C++代码模板:

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

 

模板2
当将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时,其更新操作是 r = mid - 1 或者 l = mid,此时为了防止死循环,计算 mid 时需要加1,即 mid = ( l + r + 1 ) /2。

C++代码模板:

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = ( l + r + 1 ) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

 
那么问题来了,

为什么两个二分模板的 mid 取值不同?

对于第二个模板,当我们更新区间时,如果左边界 l 更新为 l = mid,此时 mid 的取值就应为 mid = (l + r + 1)/ 2。因为当右边界 r = l + 1 时,此时 mid = (l + l + 1)/2,相当于下取整,mid 为 l,左边界再次更新为 l = mid = l,相当于没有变化。while 循环就会陷入死循环。因此,为了避免这种情况,当左边界要更新为 l = mid 时,就令 mid =(l + r + 1)/2,相当于向上取整,此时就不会因为 r 取特殊值 r = l + 1 而陷入死循环了。

而对于第一个模板,如果左边界 l 更新为 l = mid + 1,是不会出现这种情况的。

那啥时候用模板1?啥时候用模板2呢?

假设初始时的二分区间为 [l,r],每次二分缩小区间时,如果左边界 l 要更新为 l = mid,此时就要使用模板2,让 mid = (l + r + 1)/ 2,否则 while 会陷入死循环。如果左边界 l 更新为 l = mid + 1,此时就使用模板1,让 mid = (l + r)/2。因此,模板 1 和模板 2 本质上是根据代码来区分的,而非应用场景。如果写完之后发现是 l = mid,那么在计算 mid 时需要加上1,否则如果写完之后发现是 l = mid + 1,那么在计算 mid 时不加 1。

为什么模板循环条件是 while( l < r),而不是 while( l <= r)?

本质上取 l < r 和 l <= r 是没有任何区别的,只是习惯问题,如果取 l <= r,只需要修改对应的更新区间即可。

while 循环结束条件是 l >= r,为什么二分结束时优先取 r 而不是 l ?

二分的 while 循环的结束条件是 l >= r,所以在循环结束时 l 有可能会大于 r,此时就可能导致越界,二分问题优先取 r。

 
最后,熟记以上两个二分模板,基本上可以解决 90% 以上的二分问题,妈妈再也不用担心我被二分的边界取值所困扰啦。

 
 
 
不是吧大佬,又想白嫖?不过我喜欢!!

相关文章