Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Leetcode bug? (Function isn't stopping even after it returns in binary search)

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

The output is :

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

and 1 2 1 keeps repeating.
The test case is :
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

The function has printed "ret", hence shouldn’t it return and stop? I tried this on my pc, works just fine. Is this a bug?
Leetcode didn’t give an error when it’s either b > a+1 or if instead of b = mid and a = mid, it’s b =mid-1 and a =mid+1.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

>Solution :

Your code gets stuck in an infinite loop.

When a == 1 and b == 2 then mid = (1+2)/2 = 1 which makes your code take the a = mid = 1 branch and you never reach a == b.

The same happens whenever (a+b)/2 == a, ie when a + 1 == b.

The ret in the output is probably due to a second test case run by the online judge. For the first test your code returns a result but it then gets stuck on the second.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading