对于分配,我必须创建一个使用二进制搜索来查找整数的平方根的方法,如果它不是平方数,它应该返回一个整数 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 条件下,但由于平方数之间的差距随着数字变大而变得越来越大(所以我不能只说差距必须低于一个阈值)。如果有帮助的话,这个练习是关于不变量的(因此为什么要以这种方式设置)。谢谢你。