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

• (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.

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

• @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.

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