``````class Solution {
public:
int mySqrt(int x) {
int ans = 0;
for(int i = 1;i <= x;i++)
{
//avoid overflow
if(i > x / i)
return ans;
ans = i;
}

return ans;
}
};``````
``````Runtime: 68 ms, faster than 5.95% of C++ online submissions for Sqrt(x).
Memory Usage: 6.2 MB, less than 100.00% of C++ online submissions for Sqrt(x).``````

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

return r;
}
};``````

``````Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sqrt(x).
Memory Usage: 6.2 MB, less than 100.00% of C++ online submissions for Sqrt(x).``````

``````class Solution {
public:
int mySqrt(int x) {
if(x == 0 || x == 1)
return x;

long long left = 0,right = x;
while(true){
int mid =left + (right -left)/2;
if(mid  > x / mid)
right = mid - 1;
else if (mid <= x / mid){
//当前mid * mid <= x,(mid+1)*(mid+1) > x,那么mid就是要查找的答案
if(mid + 1 > x /(mid + 1))
return mid;
left = mid + 1;
}

}

return 0;
}
};``````

``````Runtime: 4 ms, faster than 55.75% of C++ online submissions for Sqrt(x).
Memory Usage: 6.1 MB, less than 63.26% of C++ online submissions for Sqrt(x).``````