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

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

因为mid * mid会溢出。您应该使用 long 以避免溢出。然后在 return 结果时将其转换回 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

这就像二分查找

以下代码计算数字的 [integer] 平方根。如果号码不是完全平方（没有整数平方根），则returns-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
  }
}

学分：破解编码面试

Answer 3

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

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

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

但更好的方法是使用Newton's method。

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

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

Finding the square root of a number by using binary search

java

binary-search

square-root