代码之家  ›  专栏  ›  技术社区  ›  NITHIN SABU

Leetcode bug?(函数即使在二进制搜索中返回后也不会停止)

  •  -2
  • NITHIN SABU  · 技术社区  · 2 年前
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int a = 0;
            int b = nums.size()-1,mid;
            while (b>a){
                mid = (a+b)/2;
                cout<<a<<" "<<b<<" "<<mid<<endl;
                if (nums[mid]==target) {
                    cout<<"ret";
                    return mid;
                }
                else if (nums[mid]>target){
                    b = mid;
                }else{
                    a = mid;
                }  
            }
            return -1;
        }
    };
    

    输出为:

    Time Limit Exceeded
    Stdout:
    0 5 2
    2 5 3
    3 5 4
    ret0 5 2
    0 2 1
    1 2 1
    1 2 1
    1 2 1
    

    1 2 1不断重复。 测试用例是: 输入:nums=[-1,0,3,5,9,12],目标=9 输出:4

    函数已经打印了“ret”,因此它不应该返回并停止吗?我在电脑上试过了,效果很好。这是个虫子吗? Leetcode在b>a+1,或者如果不是b=mid和a=mid,而是b=mid-1和a=mid+1。

    1 回复  |  直到 2 年前
        1
  •  1
  •   463035818_is_not_an_ai    2 年前

    您的代码陷入了一个无限循环。

    什么时候 a == 1 b == 2 然后 mid = (1+2)/2 = 1 这使得您的代码 a = mid = 1 树枝,你永远无法触及 a == b

    每当 (a+b)/2 == a a + 1 == b

    这个 ret 在输出中可能是由于在线法官运行的第二个测试用例。对于第一次测试,您的代码会返回一个结果,但在第二次测试时却被卡住了。