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],目标= 5.它们之间的差异是while循环中的条件语句,其中的一个bsearch2恰好是bsearch1.两者都完全正确的逻辑.我如何提前知道bsearch2"错误"？任何人都可以证明条件语句bsearch2会导致无限循环(可能在数学视图中)吗？直到现在我都找不到任何线索和证据.

编辑:我已经评估了示例A = [1,3,5,6],目标= 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,向下移动不会受此影响,事实上实际上利用了它.

为了解释这一点,bsearch2以同样的方式bsearch1利用自然的低方向偏差,不满的舍入必须在中点计算中考虑,因此它总是有利于高端.要做到这一点,请通过偏向相反方向的计算来强制排除错误.即bsearch2,这样做:

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

事实上,为了避免溢出,这应该是真的

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

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

#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

我希望这是有道理的.