非常简单的一个题，用二分法逼近求出ans即可，额外注意下溢出问题。
不过我要给自己增加难度，用long或者BigNum实现没意思，只能使用int类型
换句话当出现溢出时我们自己得检测出来
原代码（会溢出）
class Solution {
public int mySqrt(int x) {
int l = 1;
int r = x;
while (l < r) {
int mid = (l + r) / 2;// l+r会溢出
if (mid * mid == x) { // 乘法会溢出
return mid;
} else if (mid * mid < x) {
l = mid + 1;
} else {
r = mid;
}
}
if (l * l > x) l--;
return l;
}
}
两处会出现溢出，我们换种不溢出的方法实现即可了
优化代码
class Solution {
public int mySqrt(int x) {
int l = 1;
int r = x;
while (l < r) {
int mid = l / 2 + r / 2;
if (l % 2 == 1 && r % 2 == 1) {
mid++;//当两个数都是奇数时，mid需要+1
}
if (fun(mid, x) == 0) {
return mid;
} else if (fun(mid, x) < 0) {
l = mid + 1;
} else {
r = mid;
}
}
if (fun(l, x) > 0) l--;
return l;
}
// 不溢出的判断 mid^2 与x的大小
int fun(int mid, int x) {
int tmp = 0;
if (mid < 10000) {
tmp = mid * mid;//当小于10000时，直接相乘就好了
} else {
// 采用累加的形式，一旦出现负数就说明溢出了
for (int i = 0; i < mid; i++) {
tmp += mid;
if (tmp <= 0) {
return 1;
}
}
}
if (tmp > x) return 1;
if (tmp == x) return 0;
return -1;
}
}
另外一种判断方法：
// 判断 mid^2 与x的大小
int fun(int mid, int x) {
int tmp = mid * mid;
if (tmp / mid != mid) {
// 出现溢出,mid^2大
return 1;
}
if (tmp == x) return 0;
if (tmp > x) return 1;
return -1;
}