# Using binary search accepted, but one question

• ``````int sqrt(int x) {
if(x == 0 || x == 1){
return x;
}
int l = 1, r = x, res;
while(l <= r){
int m = (l + r)/2;
if(m == x / m){
return m;
}else if(m > x / m){
r = m - 1;
}else{
l = m + 1;
res = m;
}
}
return res;
}
``````

My question is:
If using `if(m * m == x)` instead of `if(m == x / m)` (and `if(m * m > x)` instead of `if(m > x / m)` ), I will get "Time Limit Exceeded" on case 2147395599. Why that happens?

• If (m * m) overflows the 32 bit int limit, you might end up with an infinite loop.

• Oh you are right, thanks!

• This can be solved with a less r ,such as :
r =(int)Math.pow(Math.pow(2,31)-1,0.5)

• It's not the point. If you use Math.pow, why not use Math.sqrt ? It's no the answer to use the Math class, and you should give an answer without Math class.

• I do not quite understand.If overflows, end the loop, then what to be returned?

• When (m * m) overflows, the search range is still cut by half if no return, even through the wrong half may be cut. So, the infinite loop is not caused by overflow of (m * m), at least directly. It is instead caused by overflow of indices, i.e., l, r, m. See the example below: (m * m) still overflows, but no infinite loop, just yields wrong answer.

In summary, overflow of (m * m) causes overflow of indices, thus cause infinite loop indirectly. In this sense, the accepted answer is at best incomplete, if not misleading.

I post my multiplication- and division-based implementations in case they may be of help.

``````class Solution {
public:
int sqrt(int x) {
if(x == 0 || x == 1){
return x;
}
long l = 1, r = x, res;
while(l <= r){
long mid = (l + r)/2;
int m = mid;
if(m * m == x){
return mid;
}else if(m * m > x){
r = mid - 1;
}else{
l = mid + 1;
res = mid;
}
}
return res;
}
};
``````

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