二进制搜索计算平方根（Java）

我需要帮助编写一个使用二进制搜索的程序来递归计算输入非负整数的平方根（向下舍入到最接近的整数）。

这是我到目前为止：

import java.util.Scanner; public class Sqrt { public static void main(String[] args) { Scanner console = new Scanner(System.in); System.out.print("Enter A Valid Integer: "); int value = console.nextInt(); calculateSquareRoot(value); } public static int calculateSquareRoot(int value) { while (value > 0) { double sqrt = (int) Math.sqrt(value); System.out.println(sqrt); } return -1; } } 

它必须使用二进制搜索来计算平方根这一事实让我感到困惑。 如果有人对如何做到这一点有任何建议，将不胜感激。 谢谢

Answer 1

Teh codez：

 def sqrt(n): low = 0 high = n+1 while high-low > 1: mid = (low+high) / 2 if mid*mid <= n: low = mid else: high = mid return low 

要理解它，只需要考虑循环不变量，即：

低低<= n <高

如果您理解这段代码，那么编写递归版本应该是微不足道的。

Answer 2

你可以使用这个java方法（Iterative）

 public class Solution { // basic idea is using binary search public int sqrt(int x) { if(x == 0 || x == 1) { return x; } int start = 1, end = x / 2; while(start <= end) { int mid = start + (end - start) / 2; if(mid == x / mid) { return mid; } if(mid < x / mid) { start = mid + 1; } else { end = mid - 1; } } return start - 1; } } 

您可以驱动自己的递归方法

Answer 3

基本上这个想法是你可以使用二进制搜索来更接近答案。

例如，假设你被给予14作为输入。 然后，您确定14的平方根在0到14之间。因此，0和14是您当前的“边界”。 你将这两个端点平分并获得中点：7。然后你尝试7作为候选者 – 如果7的平方大于14，那么你有一个新的边界（0,7）; 否则你会有一个新的边界（7,14）。

你继续重复这个二等分直到你对答案“足够接近”，例如你有一个数字平方在14-0.01和14 + 0.01之间 – 然后你宣布这个答案。

好的，那么多提示对于HW来说应该足够好了。 别忘了引用StackOverflow。

Answer 4

我假设这是作业，所以我只是给一个提示。

要进行二分搜索，请选择尽可能接近正确值的中位数的点。 因此，问题变成平方根的典型中值，即是常数还是可以通过乘法计算。 显然使用任意常量对大多数输入都不起作用，因此您需要通过将输入乘以常数来得出您的猜测。

至于要乘以的常数C应该是什么，应根据您期望的输入值来选择。 例如，如果您希望输入大约为250,000，那么：

 C * 250,000 ~= sqrt(250,000) C = sqrt(250,000) / 250,000 C = 500 / 250,000 C = 1 / 500 

Answer 5

我在你的问题中看到了两个重要的计算概念。 第一个是二分搜索，第二个是递归。 由于这是家庭作业，这里有助于理解二元搜索，递归以及如何思考它们。

将二进制搜索视为将解决方案“空间”分成两半，保持解决方案的一半并连续执行，以便该过程收敛于解决方案。 这样做的关键概念是您需要设计具有以下属性的解决方案“空间”：

1）可细分，通常为一半或至少两件

2）细分后的两个部分，有一种方法可以确定哪一半有解决方案，这样就可以只在一半上重复这个过程。

递归涉及调用自身的函数（OO中的方法）。 递归对于收敛于结论的过程非常有效。 它要么永远地递归，要么直到你耗尽一些资源，通常是记忆，并且致命地停止。 递归的两个关键概念是：

1）通过一些不变性收敛（更多关于下面的不变性）。

2）终止条件（识别充分收敛的条件）。

现在，为你的平方根例程。 例程的要求是：

1）整数输入。

2）整数平方根近似，给出最接近实际平方根的最小值。

3）使用递归。

4）使用二进制搜索。

这有助于了解一些关于平方根的数学知识。 初等微积分和分析几何概念也很有用。 让我们做一些推理。

我们有一个任意正整数x。 我们想要它的根源。 如果我们为y选择一些测试值，我们可以看看它是否是x的根，如果y * y = x。 如果y太大，y * y> x。 如果y太小，y * y

这是一些帮助的数学推理。 我们知道x = y * y其中y是x的平方根。 这意味着：y = x / y。

嗯…如果y大到x的平方根，会发生什么？ 然后：x

这会收敛吗？ 好吧，在使用正实数的数学中，平均值总是高于值，但每次迭代越接近。 这满足了我们连续将解“空间”分成两部分并知道要保留哪两部分的条件。 在这种情况下，我们连续计算低于先前值的新值，低于该值，答案仍然存在，允许我们丢弃新值之上的所有值。 当我们达到不存在高于答案的新值的条件时，我们就会停止。 然而，使用计算机导致实数的二进制近似。 对于整数，除法有截断。 这可能有利地或不利地影响收敛。 此外，您的答案应该是小于或等于平方根的最大整数。 看看我们将获得的收敛类型是明智的。

由于整数除法转折，y1 =（x / y0 + y0）/ 2将收敛，直到连续迭代达到整数根或底值（即最小整数小于）根。 这是理想的。 如果我们从根的建议值开始，必须大于根，比如x本身，yn的第一个值，其中yn * yn <= x是期望的结果。

简单的答案是，当我们从y0> y开始，第一个小于或等于y的新yn，则y – yn <1。也就是说，yn现在是我们一直在寻找的最低值我们现在有一个完全满足所需答案条件的终止条件。

这是基本的迭代和递归解决方案。 解决方案不包含安全function，以确保不输入x的负值。 一个主要的问题是如果有人想要找到0的平方根，则避免除以零。由于这是一个简单的答案，递归和迭代方法都会在除零之前返回0。 递归和迭代解决方案都适用于寻找0和1的平方根的平凡情况。

还有另一种分析总是必须用Java中的int和long算法来完成。 一个主要的问题是整数溢出，因为Java对int或long overflow没有任何作用。 溢出导致二进制补码值（在其他地方查找）可能导致伪造的结果，而Java不会抛出带有int或long溢出的exception。

在这种情况下，很容易避免算术导致内部溢出大的x值。 如果我们创建一个终止条件，例如y0 * y0 y。 x / 2适用于x> 1的所有值。由于x的平方根（其中x为0或1）只是x，我们可以轻松地测试这些值并简单地返回正确和平凡的值。 您可以构造代码以防止使用值<0或值> Integer.MAX_VALUE。 如果我们使用long而不是int，则可以应用相同的方法。 欢迎来到现实世界中的计算机！

 public static int intSqRootRecursive (int x) { // square roots of 0 and 1 are trivial and x / 2 for // the y0 parameter will cause a divide-by-zero exception if (x == 0 || x == 1) { return x; } // starting with x / 2 avoids overflow issues return intSqRootRecursive (x, x / 2); } // end intSqRootRecursive private static int intSqRootRecursive(int x, int y0) { // square roots of 0 and 1 are trivial // y0 == 0 will cause a divide-by-zero exception if (x == 0 || x == 1) { return x; } // end if if (y0 > x / y0) { int y1 = ((x / y0) + y0) / 2; return intSqRootRecursive(x, y1); } else { return y0; } // end if...else } // end intSqRootRecursive public static int intSqRootIterative(int x) { // square roots of 0 and 1 are trivial and // y == 0 will cause a divide-by-zero exception if (x == 0 || x == 1) { return x; } // end if int y; // starting with y = x / 2 avoids overflow issues for (y = x / 2; y > x / y; y = ((x / y) + y) / 2); return y; } // end intSqRootIterative 

您可以测试递归解决方案以找出将在帧堆栈上产生的实例数，但您会发现它收敛速度非常快。 有趣的是，迭代解决方案比递归解决方案小得多且速度快，通常情况并非如此，这也是为什么在可以预测堆栈资源足以用于递归深度的情况下使用递归的原因。

Answer 6

以下是使用二进制搜索的Java中的递归解决方案：

 public class FindSquareRoot { public static void main(String[] args) { int inputNumber = 50; System.out.println(findSquareRoot(1, inputNumber, inputNumber)); } public static int findSquareRoot(int left, int right, int inputNumber){ // base condition if (inputNumber ==0 || inputNumber == 1){ return inputNumber; } int mid = (left + right)/2; // if square of mid value is less or equal to input value and // square of mid+1 is less than input value. We found the answer. if (mid*mid <= inputNumber && (mid+1)*(mid+1) > inputNumber){ return mid; } // if input number is greater than square of mid, we need // to find in right hand side of mid else in left hand side. if (mid*mid < inputNumber){ return findSquareRoot(mid+1, right, inputNumber); } else{ return findSquareRoot(left, mid-1, inputNumber); } } } 

Answer 7

迭代二进制解决方案：

 public static double sqrt(int n) { double low = 0; double high = n; double mid = (high - low) / 2; while (Math.abs((mid * mid) - n) > 0.000000000001) { if ((mid * mid) > n) { high = mid; mid = (high - low) / 2; } else{ low = mid; mid = mid + ((high - low) / 2); } } return mid; } 

Answer 8

edst解决方案很好，但第11行有一个错误：

 mid = (high - low) / 2; 

应该

 mid = low + (high - low) / 2;