二进制搜索计算平方根(Java)

Question

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

这是我到目前为止:

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方法(迭代)

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

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

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

1）可以细分，通常分为两部分或至少两部分

2）在细分后的两块中，有一种方法可以确定哪一半有解，以便仅对一半重复该过程。

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

1）通过一些不变性进行收敛（下面详细介绍不变性）。

2) 终止条件（承认足够收敛的条件）。

现在，开始您的平方根例程。例程的要求是：

1) 整数输入。

2) 整数平方根近似，给出最接近实际平方根的下取整整数。

3）使用递归。

4）使用二分查找。

了解一些关于平方根的数学知识对此很有帮助。基本微积分和解析几何概念也很有帮助。让我们做一些推理。

我们有一个任意正整数 x。我们想要它的根 y。如果我们为 y 选择一些测试值，如果 y * y = x，我们可以看看它是否是 x 的根。如果 y 太大，则 y * y > x。如果 y 太小，则 y * y < x。我们还知道 0 <= root <= x 并且 0 和 1 的平方根通常为零和 1。由于我们正在寻找 y * y <= x（即下限值）的最大整数，因此我们将有也要考虑到这一点。

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

嗯...如果 y 太大而无法成为 x 的平方根，会发生什么？那么： x < y * y 并且： x/y < y 这意味着 x/y 也太小而不能作为 x 的平方根。所以我们知道，当 y 太大时，x/y < x < y 的平方根。因此，让我们在 x/y 和 y 之间找到一个新的 y（例如 y1）作为新的测试值。x/y 和 y 的平均值即可。如果 y0 太大，y1 = (x/y0 + y0)/2 将给出比 y0 更接近 x 的平方根的 y1。

这收敛了吗？嗯，在使用正实数的数学中，平均值将始终高于该值，但每次迭代都会变得更接近。这满足了我们依次将解“空间”分为两部分并知道保留两部分中的哪一个的条件。在这种情况下，我们连续计算出低于先前值的新值，并且答案仍然低于该值，从而允许我们丢弃高于新值的所有值。当我们达到一个条件，即不再存在高于答案的新值时，我们就会停止。然而，使用计算机会产生实数的二进制近似值。对于整数，除法中存在截断。这可能对收敛产生有利或不利的影响。另外，你的答案应该是小于或等于平方根的最大整数。明智的做法是看看我们将获得什么样的融合。

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

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

这是基本的迭代和递归解决方案。该解决方案不包含安全功能来确保 x 不会输入负值。一个主要问题是避免除以零，以防有人想要求 0 的平方根。由于这是一个微不足道的答案，因此递归和迭代方法在除以零之前都会返回 0。递归和迭代解决方案都适用于查找 0 和 1 的平方根的简单情况。

还有一个分析总是必须用Java中的int和long算术来完成。主要问题是整数溢出，因为 Java 对 int 或 long 溢出不做任何处理。溢出会产生二进制补码值（请在其他地方查找），这可能会导致虚假结果，并且 Java 不会因 int 或 long 溢出而引发异常。

在这种情况下，很容易避免可能导致 x 值较大时发生内部溢出的算术。如果我们创建一个终止条件，例如 y0 * y0 < x，如果 x 大于 Integer.MAX_VALUE 的平方根，我们就会面临溢出的风险，因为中间值 y0 * y0 将立即超过最大 int 值。然而，我们可以将终止条件重新安排为 y0 < x / y0。我们仍然有一个计算问题：((x / y0) + y0) / 2) 如果 x 和 y0 是 Integer.MAX_VALUE，因为它会尝试 Integer.MAX_VALUE + 1。但是，我们总是可以从小于的值开始x 保证 > 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

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