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 不可能是消极的。这是你的循环条件，这就是循环永远不会结束的原因。

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