使用二叉搜索查找数字的平方根

Question

我尝试使用二叉搜索来查找整数的平方根，但有些我无法通过一些测试用例。

我能够通过 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;
}

Answer 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);
}

Answer 2

这是一个处理双打的版本。

• 它是递归的。
• 它会计算直到达到给定的精度。

for (int i = 2; i < 10; i++) {
System.out.println("sqrt("+i+") = " + sqrt(i));
}

指纹

sqrt(2) = 1.414213562373095
sqrt(3) = 1.7320508075688772
sqrt(4) = 2.0
sqrt(5) = 2.23606797749979
sqrt(6) = 2.449489742783178
sqrt(7) = 2.6457513110645907
sqrt(8) = 2.82842712474619
sqrt(9) = 3.0

public static double sqrt(double i) {
return bsqrt(i, 0, i, 0);
}
static double prec = 10E-200;   
private static double abs(double d)  {
return d < 0 ? -d : d;
}
private static double bsqrt(double i, double low, double high,
double last) {
double mid = (high + low) / 2;
double d = last - mid;
if (d < 0) {
d = -d;
}
if (d < prec) {
return mid;
}
double sqr = mid * mid;
if (sqr < i) {
return bsqrt(i, mid, high, mid);
} else {
return bsqrt(i, low, mid, mid);
}
}

但更好的方法是使用牛顿的方法。

static double prec = 10E-15;
public static double newtons(double i) {
// initial guess
double x = i / 2;
double d = i;
double nx = 0;
while (abs(d) > prec) {
nx = x - (x*x - i)/(2*x);
d = nx - x;
x = nx;
}
return nx;
}

Answer 3

Java 中使用二叉搜索算法的平方根计算

使用

二叉搜索进行平方根计算的

---

伪代码流：

1. 初始化变量、开始和结束以跟踪搜索范围。
2. 计算中间指数中间值作为开始和结束的平均值。
3. 只要开始小于或等于结束，就进入 while 循环。
4. 检查中间索引的平方是否等于目标数字：
   • 如果为 true，则将 mid 分配给 ans，并返回 ans 作为平方根。
   • 如果 mid 的平方大于目标数字：
5. 将 end 更新为 mid-1 以在范围的下半部分进行搜索。
   • 如果 mid 的平方小于或等于目标数字：
6. 将 ans 更新为 mid 作为潜在的平方根候选项。
7. 将开始更新为中间 + 1 以在范围的上半部分搜索。
8. 重新计算 mid 作为更新的开始和结束的平均值。
9. 重复步骤 4-7，直到搜索范围用尽(开始大于结束(。
10. 返回 ans 作为搜索期间找到的最接近的平方根。

迭代方法

public static int findSquareRoot(int num){
int ans = -1;
int startIndex = 0;
int endIndex = num;
long midIndex = startIndex + (endIndex - startIndex ) / 2;
while (startIndex <= endIndex){
if((midIndex*midIndex) == num){
ans = (int )midIndex;
return ans;
} else if ((midIndex*midIndex) > num) {
endIndex = (int) midIndex - 1;
}else {
ans = (int) midIndex;
startIndex = (int) midIndex + 1;
}
midIndex = startIndex + (endIndex - startIndex ) / 2;
}
return ans;
}

了解全面的解决方案 https://github.com/Amir36036/ds/blob/array/src/main/java/org/ds/array/FindSquareRootByBinarySearch.java

Answer 4

这就像一个二叉搜索

以下代码计算数字的 [整数] 平方根。如果数字不是 完全平方(没有整数平方根(，则返回 -1。它通过连续 猜。如果 n 为 100，则首先猜测 SO。太高了？尝试较低的方法 - 介于 1 之间 等等。它的运行时是什么？

int sqrt(int n) {
return sqrt_helper(n, 1, n);
}
int sqrt_helper(int n, int min, int max) {
if (max < min) return -1; // no square root
int guess = (min + max) / 2·,
if (guess *guess == n) { // found it!
return guess;
}else if (guess * guess < n) { II too low
return sqrt_helper(n, guess + 1, max); // try higher
} else { // too high
return sqrt_helper(n, min, guess - l); //try lower
}
}

学分：破解编码面试