0%

[转载] 二分查找中的死循环

注:转载自 二分查找中的死循环 - 小白菜又菜 - CSDN博客

二分算法是我们经常会用到的一个算法。它是分治法的一个应用。不过,虽然他写起来貌似很简单,但是却很容易写错。下面我们讨论一下二分的死循环问题。(这里讨论的是整数的二分问题,浮点数的二分不容易死循环)

查找的元素确定,值唯一或者不存在

这种情况等下,我们的流程分为三个分支:(相等、小于、大于)。这类不容易死循环,代码如下:

if (data[mid] == key)
    return mid;
if (data[mid] > key)
    r = mid-1;
else l = mid+1;

被查元素不确定,值可能有多个,找到第一个或者最后一个

这是最容易出现死循环的情况,也是本文讨论的核心。这种情况下,流程分成两个分支,我们分两种情况讨论:

a.取第一个小于 key 的元素:

if (data[mid] >= key)
    r = mid-1;
else l = mid;

我们看式子 mid = (l+r)/2

  • 如果(l+r)为奇数,则
    • mid = (l+r)/2 = (l+r-1)/2 导出 2*mid = (l+r-1)/2*2 = l+r-1
    • 这时,若 mid = l 则“else l = mid;”这句代码就会就会进入死循环。
    • 所以这时使用 mid = (l+r+1)/2 代替 mid = (l+r+1)/2 就不会死循环了。
  • 如果(l+r+1)为偶数,则
    • mid = (l+r+1)/2 = (l+r)/2 导出 2*mid = (l+r)/2*2 = l+r 不会出现问题。
    • (这时使用 mid = (l+r)/2 也不会死循环)
  • 综上,这种情况下使用 mid = (l+r+1)/2

就不会死循环了,不过这不是通用式子,看 b 情况。

int bs(int l, int r, int key)
{
    while (l < r) {
        int mid = (l+r+1)/2;
        if (data[mid] >= key)
            r = mid-1;
        else
            l = mid;
    }
    return l;
}

b.取第一个大于 key 的元素:

if (data[mid] <= key)
    l = mid+1;
else r = mid;

我们看式子 mid = (l+r+1)/2

  • 如果(l+r+1)为奇数,则
    • mid = (l+r+1)/2 = 导出 2*mid = (l+r+1)/2*2 = l+r+1
    • 这时,若 mid = r 则“else r = mid;”这句代码就会就会进入死循环。
    • 所以这时要使用 mid = (l+r)/2 代替 mid = (l+r+1)/2 才不会死循环了。
  • 如果(l+r)为偶数,则
    • mid = (l+r)/2 导出 2*mid = (l+r)/2*2 = l+r不会出现问题。
    • (这时使用 mid = (l+r+1)/2 也不会死循环)
  • 综上,这种情况下使用 mid = (l+r)/2 就不会死循环了。
int bs(int l, int r, int key)
{
    while (l < r) {
        int mid = (l+r)/2;
        if (data[mid] <= key)
            l = mid+1;
        else r = mid;
    }
    return r;
}

c.综合 a、b 得到结论取中值的计算方式与判断条件有关,下面加入一个小优化。

一步小优化,防止溢出

这里使用 mid = l+(r-l)/2 代替 mid = (l+r)/2 以及 mid = l+(r-l+1)/2 代替 mid = (l+r+1)/2。这样可以防止 l+r 和 l+r+1 溢出。下面证明两者的等价性。

  • a.l+r 为奇数,则 r-l 为奇数,r-l+1 为偶数
    • mid = l+(r-l+1)/2 = l*2/2 + (r-l+1)/2 = (l+r+1)/2
    • mid = l+(r-l)/2 = l*2/2 + (r-l-1)/2 = (r+l-1)/2 = (r+l)/2
  • b.l+r 为偶数,则 r-l 为偶数,r-l+1 为奇数
    • mid = l+(r-l+1)/2 = l*2/2 + (r-l)/2 =(l+r)/2 = (l+r+1)/2
    • mid = l+(r-l)/2 = l*2/2 + (r-l)/2 = (l+r)/2
  • c.综上所述上述替代成立。
  • 本文作者: rcxzsc
  • 本文链接: https://rcxzsc.com/archives/655/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY 许可协议。转载请注明出处!