C:两种不同的二分搜索实现，一种陷入死循环

Question

这里有两个“健忘”二分搜索的实现，因为它们在完成之前不会检查精确匹配。

1)

int bsearch1(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = (low + high) >> 1;
        if (target > A[mid])
            low = mid + 1;
        else
            high = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

2)

int bsearch2(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = (low + high) >> 1;
        if (target < A[mid])
            high = mid - 1;
        else
            low = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

注意:n是数组A的长度，target是要查找的元素。

bsearch1 工作正常，但 bsearch2 遇到无限循环，例如 A=[1,3,5,6]，target=5。它们之间的区别在于while循环中的条件语句，bsearch2中的条件语句与bsearch1正好相反。两者在逻辑上都是完全正确的。我怎样才能提前知道 bsearch2 是“错误的”？谁能证明bsearch2中的条件语句会导致无限循环(也许从数学角度看)？直到现在我也找不到任何线索和证据。

编辑: 我评估了例子A=[1,3,5,6], target=5的整个过程:

1.low = 0, high = 3, mid = 1, A[mid] = 3
2.low = 1, high = 3, mid = 2, A[mid] = 5
3.low = 2, high = 3, mid = 2, A[mid] = 5
...
n.low = 2, high = 3, mid = 2, A[mid] = 5

我发现bsearch2达不到low == high这个条件，因此无法退出while循环。但是不知道为什么low和high都达不到low == high 最后喜欢bsearch1.

Answer 1

一旦遇到 high == (low+1) 的分区，您的第二个算法就会出现重复循环。当发生这种情况时，您实际上得到了 mid = (low + low + 1)/2，这相当于 (2*low)/2 + 1/2。使用整数除法，结果为 mid = low + 0。由于您在低侧的唯一移动是 low = mid，但它们已经相等，因此您有一个无限循环。

在第一次实现时没有发生这种情况的原因是整数除法损失的方向。它总是向下。因此 high moving down 不会受此影响，事实上 确实利用了它。

要在 bsearch2 中考虑这一点，就像 bsearch1 利用自然的低方向偏差一样，必须在中点考虑不满意的舍入计算，因此它总是向高端移动。为此，通过在相反方向上偏置计算来强制消除错误。 IE。对于 bsearch2，执行此操作:

mid = (low + high + 1) >> 1;

说实话，为了避免溢出，这确实应该是

mid = low + ((high - low + 1) >> 1);

这将实现与 bsearch1 调整 bsearch2 中点相同的效果。一个例子值得注意:

#include <stdio.h>

int bsearch2(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = low + ((high - low + 1) >> 1);
        if (target < A[mid])
            high = mid - 1;
        else
            low = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

int main()
{
    // build a sorted array from 1...20
    int A[20];
    for (int i=0; i<sizeof(A)/sizeof(*A); ++i)
        A[i] = i+1;

    for (int i=0; i<=sizeof(A)/sizeof(*A)+1; ++i)
        printf("Search for %d found index %d\n", i, bsearch2(A, sizeof(A)/sizeof(*A), i));

    return 0;
}

输出

Search for 0 found index -1
Search for 1 found index 0
Search for 2 found index 1
Search for 3 found index 2
Search for 4 found index 3
Search for 5 found index 4
Search for 6 found index 5
Search for 7 found index 6
Search for 8 found index 7
Search for 9 found index 8
Search for 10 found index 9
Search for 11 found index 10
Search for 12 found index 11
Search for 13 found index 12
Search for 14 found index 13
Search for 15 found index 14
Search for 16 found index 15
Search for 17 found index 16
Search for 18 found index 17
Search for 19 found index 18
Search for 20 found index 19
Search for 21 found index -1

我希望这是有道理的。