首页 文章

C：两个不同的二进制搜索实现，一个陷入无限循环

提问于
浏览 次
5

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

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 是"wrong"？任何人都可以证明 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 .

c algorithm binary-search

4 回答

  • 7

    一旦遇到 high == (low+1) 的分区，您的第二个算法就会遇到重复周期 . 当发生这种情况时，你基本上有 mid = (low + low + 1)/2 ，相当于 (2*low)/2 + 1/2 . 使用整数除法，结果为 mid = low + 0 . 由于你唯一的低位运动是 low = mid ，但它们已经是等价的，你有一个无限循环 .

    在第一次实现时不会发生这种情况的原因是整数除法的方向 . 它总是下降 . 因此，向下移动不会受此影响，事实上实际上利用了它 .

    为了在_930196中解释这一点， bsearch1 利用自然的低方向偏差，在中点计算中必须考虑不满的舍入，因此它总是有利于高端 . 要做到这一点，请通过偏向相反方向的计算来强制排除错误 . 即对于 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;
}

    Output

    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

    我希望这是有道理的 .

    回复于
  • 0

    当你第二次进入循环时，低是1，高是3，所以mid是2 .

    在while循环中，没有“相等”检查，所以发生的事情是每次目标（5）实际上等于A [mid]，所以你被困在while循环中 .

    进入时加入不等于目标检查

    while (low<high && A[mid]!=target) {
…
}

    它应该工作 .

    回复于
  • 0

    首先，运行第二个算法，等到它陷入无限循环 . 然后设置一个断点并查看当前值，如 mid ， high 和 low .

    我认为 mid 超低并且取负值 . 所以试试这个代码：

    high = mid - 1 >= 0 ? mid - 1 : 0;
    回复于
  • 0

    所以基本上它是由int类型划分的属性引起的 . 在你的情况下“转移” . 他们赞成“低”而不是“高” . 这在逻辑中是看不到的 . 结论是，如果你不想使用复杂的if（l == r-1），（==）？ ：......事情，你总是把高而不是低，移到中间 . 即，高=中 . 谢谢你的提问 .

    此外，在“带有重复的旋转排序数组”的问题中，在中间== A [高]的角落，我们想做 - 高 . 实际上我们将mid比较为A [high]，而不是A [L]，因为移动高是一直是更好的选择 .

    https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

    bool search(vector<int>& nums, int target) {
    //the key of binary search  
    //1. l and r have to always "squeeze" the target. That is how we move r and l, and how we consider to do r = m or r = m-1 (see 378. Kth Smallest Element in a Sorted Matrix )
    //             if(count < k) { l = midv+1;}             else { r = midv;}
    //2. Try to exclude half of the data 
    int l = 0, r = nums.size()-1;
    int m, mval;

    while(l<=r) {
        m = l + ((r-l)>>1), mval = nums[m];
        if (mval == target) return true;
        if( mval < nums[r]) { //first see where the pivot is
           if(mval < target && target <= nums[r]) l = m+1;
           else r = m-1;
        } else if ( mval > nums[r] ) {
            if(nums[l] <= target && target < mval) r = m-1;
            else l = m+1;
        } else {//mval == nums[r], cannot decide pivot 
            --r; //move r while still be confident taht target is still in between
        }
    }
    return false;
}
    回复于

相关问题