LeetCode二分搜索函数已return却仍执行？超时异常疑惑

问题背景 #

提交至LeetCode的二分搜索代码在特定场景下出现超时，本地运行目标存在的测试用例正常，但LeetCode上无法终止。测试用例为输入nums = [-1,0,3,5,9,12]，target = 9，预期输出4。

提交代码 #

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;
    }
};

运行结果 #

LeetCode显示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

可见代码已经打印ret并执行return，但后续出现了重复的1 2 1输出，看似函数未停止。修改循环条件为b > a+1，或边界更新改为b = mid-1、a = mid+1时，LeetCode运行无异常。

问题分析与结论 #

这不是LeetCode的bug，是你的二分搜索逻辑存在死循环漏洞：

• 当a=1、b=2时，mid=(1+2)/2=1，如果此时nums[mid] < target，会执行a=mid，也就是a仍为1，循环条件b>a（2>1）依然成立，下一次循环mid还是1，直接触发无限循环。
• 本地运行正常是因为你只测了目标存在的场景（比如target=9），但LeetCode会运行多组测试用例，包括目标不存在的情况，这时候就会触发死循环。
• 你看到ret之后又出现新输出，是因为LeetCode在同一个进程中运行多个测试用例，前一个测试用例的cout输出还没刷新，下一个测试用例就启动了，并非return没生效。

解决方法：

• 方法1：修改边界更新逻辑，当nums[mid] > target时设b = mid-1，nums[mid] < target时设a = mid+1，同时循环条件改为a <= b。
• 方法2：保持原边界更新方式，将循环条件改为b > a+1，循环结束后单独判断a或b位置的元素是否等于目标。

内容的提问来源于stack exchange，提问作者NITHIN SABU