Leetcode bug？ （即使在二分搜索中返回后，函数也不会停止）

Question

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”，因此它不应该返回并停止吗？我在我的电脑上尝试过这个，效果很好。这是一个错误吗？ 当 b > a+1 或 b = mid 和 a = mid 而是 b = mid-1 和 a = mid+1 时，Leetcode 不会给出错误。

Answer 1

由于整数运算，您的代码陷入无限循环。

当

a == 1

和

b == 2

然后

mid = (1+2)/2 = 1

时，这会使您的代码采用

a = mid = 1

分支，而您永远不会到达

a == b

。

每当

(a+b)/2 == a

时都会发生同样的情况。

输出中的

ret

可能是由于在线法官运行的第二个测试用例造成的。对于第一个测试，您的代码返回一个结果，但随后卡在第二个测试上。