13

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

这是我到目前为止所拥有的：

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;
    }
}

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

4

8 回答 8

28

编码：

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 < 高高

如果您了解此代码，编写递归版本应该是微不足道的。

于 2010-09-22T04:39:14.417 回答
11

你可以使用这个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;
    }
}

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

于 2015-03-19T20:31:37.240 回答
10

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

例如，假设您有 14 作为输入。然后，您确定 14 的平方根介于 0 和 14 之间。因此，0 和 14 是您当前的“边界”。您将这两个端点一分为二并获得中点： 7. 然后您尝试将 7 作为候选 - 如果 7 的平方大于 14，则您有一个新边界 (0,7)；否则你会有一个新的边界（7,14）。

您不断重复此二等分，直到您“足够接近”答案，例如，您有一个在 14-0.01 和 14+0.01 内的数平方 - 然后您将其声明为答案。

好的，这么多的提示对硬件来说应该足够好了。不要忘记引用 StackOverflow。

于 2010-09-22T03:09:37.247 回答
4

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

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

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

C * 250,000 ~= sqrt(250,000)
C = sqrt(250,000) / 250,000
C = 500 / 250,000
C = 1 / 500
于 2010-09-22T03:03:59.043 回答
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 的平方根通常是 0 和 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 <= x 的 yn 的第一个值就是期望的结果。

简单的答案是，当我们从 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 为 0 或 1 的 x 的平方根就是 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

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

于 2012-08-14T22:22:56.357 回答
3

这是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);
        }

    }
}
于 2015-08-20T05:59:51.980 回答
1

迭代二进制解决方案：

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;
}
于 2013-01-14T07:58:13.560 回答
1

edst解决方案不错，但是第11行有错误：

mid = (high - low) / 2;

应该

mid = low + (high - low) / 2;
于 2013-09-13T09:50:42.623 回答