两个思路：
二分法：sqrt = a / mid，判断sqrt == mid
牛顿迭代法：x = (x * x/a)/2，判断x*x > a
三、解题方法
3.1 Java实现-二分法
public class Solution2 {
public int mySqrt(int a) {
// 注意：单独考虑0，防止除以0的情况
if (a == 0) {
return 0;
}
int left = 1;
int right = a;
int mid;
int sqrt;
// 注意：条件是 <=
while (left <= right) {
// 注意：这样写可以防止溢出
mid = left + (right - left) / 2;
sqrt = a / mid;
if (sqrt == mid) {
// 直接返回，mid就是平方根
return mid;
} else if (mid > sqrt) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
}
3.2 Java实现-牛顿迭代法
public class Solution {
public int mySqrt(int a) {
// 防止int越界，用long来存储乘法结果
long x = a;
while (x * x > a) {
x = (x + a / x) / 2;
}
return (int) x;
}
}
四、总结小记
两个思路：
二分法：sqrt = a / mid，判断sqrt == mid
牛顿迭代法：x = (x * x/a)/2，判断x*x > a
三、解题方法
3.1 Java实现-二分法
public class Solution2 {
public int mySqrt(int a) {
// 注意：单独考虑0，防止除以0的情况
if (a == 0) {
return 0;
}
int left = 1;
int right = a;
int mid;
int sqrt;
// 注意：条件是 <=
while (left <= right) {
// 注意：这样写可以防止溢出
mid = left + (right - left) / 2;
sqrt = a / mid;
if (sqrt == mid) {
// 直接返回，mid就是平方根
return mid;
} else if (mid > sqrt) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
}
3.2 Java实现-牛顿迭代法
public class Solution {
public int mySqrt(int a) {
// 防止int越界，用long来存储乘法结果
long x = a;
while (x * x > a) {
x = (x + a / x) / 2;
}
return (int) x;
}
}
四、总结小记
