1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int mySqrt(int x) {
long r = x;
while(r * r > x)
{
r = (r + x / r) / 2;
}
return r;
}
};
|
binary search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int mySqrt(int x) {
int lo = 0, hi = x;
while(lo < hi)
{
int mid = lo + (hi - lo) / 2 + 1;
if(mid <= x / mid)
lo = mid;
else
hi = mid - 1;
}
return hi;
}
};
|
Tips:usemid > x / mid instead of mid * mid > x, because of the overflow