文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Sqrt(x)
2. Solution
- Binary Search
class Solution {
public:
int mySqrt(int x) {
int left = 0;
int right = x;
while(left <= right) {
long mid = (left + right) / 2;
long square = mid * mid;
if(square == x) {
return mid;
}
if(square > x) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return right;
}
};
- Newton's Method
class Solution {
public:
int mySqrt(int x) {
long y = x;
while(y * y > x) {
y = (y + x / y) / 2;
}
return y;
}
};
