# Two typical solutions in C++, well-explained

• ### Solution

#### Binary search

Directly, we will go to binary search but as for integer sqrt there is one thing should be aware of: sqrt(5)=2 which indirectly gives us hint we should keep the smaller in binary searching but if we do, we will encounter TLE in case `1`. As a result, we will not keep the smaller and when we end our searching, we will check it again to return the right value. Besides to avoid overflow, we will use long instead of int.

Note to avoid infinite loop, we actually should make sure the `m` will be neither the `l` nor `r` when the next half is about `l=m or r=m`.

``````class Solution
{
public:
int mySqrt(int x)
{
long l = 0, h = x;
while(l <= h)
{
long m = l+((h-l)>>1), t = m*m;
if(t == x) return m;
if(t > x) h = m-1;
else l = m+1;
}
return l*l>x? l-1:l;
}
};
``````

#### Newton's method

This is a math solution which is presented as follows; remember to use `long` to avoid overflow.
For more details about methods of computing square roots including Newton's method.

``````class Solution
{
public:
int mySqrt(int x)
{
long g = x;
while(g*g > x) g = (g+x/g)/2;
return g;
}
};
``````

Always welcome new ideas and `practical` tricks, just leave them in the comments!

• The binary search method does not work for the input 2147483647, it returns 46341 whereas the expected result is 46340.

It is a minor issue of the loop condition, instead of `while(l<=h)` it should be `while(l<h)`

Very nice solution, a lot better than my first attempt which went something along the lines of `for(int i=1; i*i<x;i++)`

Thanks

• @atyagi12 Good point, I've updated it with `long` now. Thank you.

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