java - 平方根的二进制搜索[作业]

Question

对于分配，我必须创建一个使用二进制搜索来查找整数的平方根的方法，如果它不是平方数，它应该返回一个整数 s 使得 s*s <= 数字（所以对于 15 它将返回 3)。到目前为止我的代码是

public class BinarySearch {

    /**
     * Integer square root Calculates the integer part of the square root of n,
     * i.e. integer s such that s*s <= n and (s+1)*(s+1) > n
     * requires n >= 0
     *
     * @param n number to find the square root of
     * @return integer part of its square root
     */
    private static int iSqrt(int n) {
        int l = 0;
        int r = n;
        int m = ((l + r + 1) / 2);

        // loop invariant
        while (Math.abs(m * m - n) > 0) {
            if ((m) * (m) > n) {
                r = m;
                m = ((l + r + 1) / 2);
            } else {
                l = m;
                m = ((l + r + 1) / 2);
            }
        }
        return m;
    }

    public static void main(String[] args) {
        //gets stuck
        System.out.println(iSqrt(15));
        //calculates correctly
        System.out.println(iSqrt(16));
    }
}

这会为平方数返回正确的数字，但会陷入其他整数的无限循环。我知道问题出在 while 条件下，但由于平方数之间的差距随着数字变大而变得越来越大（所以我不能只说差距必须低于一个阈值）。如果有帮助的话，这个练习是关于不变量的（因此为什么要以这种方式设置）。谢谢你。

Answer 1

想一想：Math.abs(m*m-n) > 0总是真正的非平方数，因为它永远不会是零，.abs也不可能是负数。这是你的循环条件，这就是循环永远不会结束的原因。

这是否为您提供了足够的信息让您继续前进？

Answer 2

您需要更改while (Math.abs(m * m - n) > 0)以允许误差范围，而不是像现在那样要求它完全等于零。

尝试while((m+1)*(m+1) <= n || n < m * m)

Answer 3

#define EPSILON 0.0000001
double msqrt(double n){
    assert(n >= 0);
    if(n == 0 || n == 1){
       return n;
     }
    double low = 1, high = n; 
    double mid = (low+high)/2.0;
    while(abs(mid*mid - n) > EPSILON){
       mid = (low+high)/2.0;
       if(mid*mid < n){
          low = mid+1;
       }else{
          high = mid-1;
       }
     }
return mid;}

正如你在上面看到的，你应该简单地应用二分搜索（二分法），你可以最小化 Epsilon 以获得更准确的结果，但运行需要更多时间。编辑：我用 C++ 编写了代码（对不起）

Answer 4

正如 Ken Bloom 所说，你必须有一个错误码，1。我已经测试了这段代码，它按预期运行 15。你还需要使用浮点数，我认为这个算法对于 int 是不可能的（虽然我有没有数学证明）

private static int iSqrt(int n){
float l = 0;
float r = n;
float m = ((l + r)/2);


while (Math.abs(m*m-n) > 0.1) {
    if ((m)*(m) > n) {
        r=m;
        System.out.println("r becomes: "+r);


    } else {
        l = m;
        System.out.println("l becomes: "+l);

    }
    m = ((l + r)/2);
    System.out.println("m becomes: "+m);
}

return (int)m;

}