题目描述
实现计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例
输入: 4
输出: 2
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
解题思路
本题是典型的二分查找问题，故套用二分查找的模板，但是却有一些细节需要注意，优化前代码如下所示
public int mySqrt(int x) {
int left=0;
int right=x;
while(right>=left){
int mid=(left+right)/2;
if(mid*mid == x){
return mid;
}else if(mid*mid < x){
left = mid+1;
}else{
right = mid-1;
}
}
return right;
}
优化
之前在写二分查找相关内容的时候，我就记录过int mid=(left+right)/2;这里最好写成int mid=(left+right) >>> 1;，因为这样可以有效防止整型溢出的问题，但是由于这个问题出现可能性不高，故没有引起重视，这次的上述代码中，mid*mid则就易出现溢出问题，故本文代码应该修改为如下所示
public int mySqrt(int x) {
if(x == 0){
return 0;
}
if(x == 1){
return 1;
}
int left=0;
int right=x;
while(right>=left){
int mid=(left+right) >>> 1;
if(x/mid == mid){
return mid;
}else if(x/mid > mid){
left = mid+1;
}else{
right = mid-1;
}
}
return right;
}
因为将乘法改为了除法，解决了内存溢出问题，但是除法也应该相应的注意边界问题，以免x/mid中被除数mid的值为0
