题目
算法
* 直接模拟
* 牛顿迭代
代码
* 直接模拟
// Binary Search
class Solution {
public:
int sqrt(int x) {
long long left = 0, right = (x / 2) + 1;
while (left <= right) {
long long mid = (left + right) / 2;
long long sq = mid * mid;
if (sq == x) return mid;
else if (sq < x) left = mid + 1;
else right = mid - 1;
}
return right;
}
};
* 牛顿迭代
// Newton's method
class Solution {
public:
int sqrt(int x) {
if (x == 0) return 0;
double res = 1, pre = 0;
while (res != pre) {
pre = res;
res = (res + x / res) / 2;
}
return int(res);
}
};