我尝试使用二进制搜索来找到整数的平方根,但是有些方法无法通过一些测试用例。
我能够通过mySqrt(4)= 2,但我无法通过mySqrt(2147395599)
关于我搞砸的地方有什么想法吗?
public static int mySqrt(int x) {
int left = 0;
int right = x;
if(x < 2){
return x;
}
while(left < right){
int mid = left + ((right - left) / 2);
if(mid * mid == x){
return mid;
}
else if(mid * mid < x){
left = mid + 1;
}
else{
right = mid;
}
}
return left - 1;
}
因为中*中会溢出。您应该使用很长时间以避免溢出。然后在返回结果时将其强制转换为int。
试试这个代码
public static int mySqrt(int x) {
long left = 0;
long right = x;
if(x < 2){
return x;
}
while(left < right){
long mid = left + ((right - left) / 2);
if(mid * mid == x){
return (int)mid;
}
else if(mid * mid < x){
left = mid + 1;
}
else{
right = mid;
}
}
return (int)(left - 1);
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句