[testcase too weak] Some shared binary search solutions are buggy.


  • 0

    (Not sure if anyone brought this up before, though)
    The code like this is pretty common in some solution sharing and also passes judge, but it is actually buggy:

        bool isPerfectSquare(int num) {
            if(num<=0) return !num;
            int lo = 1, hi = num;
            while(lo <= hi) {
                auto mid = lo + (hi-lo)/2;
                if(mid*mid == num) return true; // do you see the problem???
                if(num/mid < mid) hi = mid-1;
                else lo = mid+1;
            }
            return false;
        }
    

    The code like this doesn't take overflow into consideration; try to run the code with input 131073, and you will see the mismatch.

    2 ways to solve the issue. One is to use long long instead of just int :

    long long lo=1, hi = num;
    

    This is not a general solution; which is not gonna work if the problem input is long long already.

    The second one is to change the first if statement like this:

     if(num/mid == mid && num % mid == 0) return true;//C++03 paragraph 5.6 clause 4
    

    Maybe I'm too picky? But I don't think 7~8 incorrect result per million integers is a reliable code.


  • 0
    M

    I think the testcase have been changed. And the upper bound can be initialized as sqrt(INT_MAX)


  • 0

    @MarathonRush the solution I posted still passes OJ.
    And yes, upper bound can be initialized as sqrt(INT_MAX), but you cannot use built-in sqrt(x), so you have to do some pencil&paper work to know that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.