公式
牛顿迭代法
二分
class Solution {
public:
int mySqrt(int x) {
// 注意题目的意思就相当于对double下取整数
// 但我们不能用double,因为double精度不准确
// sqrt(4)=2,但在double上可能是1.99999999....
// 使用整数时要避免溢出的情况
// 由于是下取整,因此答案是<=的情况,故left bound二分
int l = 0, r = x;
while(l < r) {
int mid = l + (r - l) / 2; // 避免溢出
if(mid >= x / mid) // 避免溢出
r = mid;
else l = mid + 1;
}
return l;
}
};