image.png
求平方根的基础在于二分查找
long mid = (left + right) / 2;//为什么mid要为long，因为midmid可能超出int的范围，mid为long，那midmid也会自动转换为long，这样就保证不会超出int，也可以单独给mid*mid转换为long
二分查找如果找不到刚好相等的平方根，就返回right,而不是mid
最好是自己去试一下，也不是绝对的
image.png
//java
public class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
long mid=0;
while (left <=right) {
mid = (left + right) / 2;//为什么mid要为long，因为mid*mid可能超出int的范围，mid为long，那///////////mid*mid//也会自动转换为long，这样就保证不会超出int，也可以单独给mid*mid转换为long
if (mid * mid == x)
return (int) mid;
else if (mid * mid < x)
left = (int) (mid + 1);
else
right = (int) (mid - 1);
}
return right;
}
}
网友评论