### 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.

Noteto 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!