二分搜索计算平方根 (Java)

Binary Search to Compute Square root (Java)

提问by NuNu

I need help writing a program that uses binary search to recursively compute a square root (rounded down to the nearest integer) of an input non-negative integer.

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

This is what I have so far:

这是我到目前为止：

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

The fact that it has to use binary search to compute the square root is the part that is confusing me. If anyone has any suggestions on how to do this, it would be greatly appreciated. Thank you

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

采纳答案by Sheldon L. Cooper

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

To understand it, just think of the loop invariant, namely:

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

lowlow <= n < highhigh

低低 <= n < 高高

If you understand this code, writing a recursive version should be trivial.

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

回答by AlcubierreDrive

I'm assuming this is homework so I'm only going to give a hint.

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

To conduct a binary search, you pick a point as close as possible the median of possible correct values. So the question becomes what is a typical median value for a square root, that is either constant or can be computed via multiplication. Obviously using an arbitrary constant will not work for most inputs, so you need to arrive at your guess by multiplying the input by a constant.

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

As for what that constant C to multiply by should be, that should be chosen based on what values you expect as input. For example, if you expect your inputs to be around 250,000, then:

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

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

回答by Amrinder Arora

Essentially the idea is that you can use binary search to get closer to the answer.

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

For example, say you are given 14 as an input. Then, you are sure that the square root of 14 is between 0 and 14. So, 0 and 14 are your current "boundaries". You bisect these two end points and obtain the mid point: 7. Then you try 7 as a candidate - If the square of 7 is greater than 14, then you have a new boundary (0,7); otherwise you would have a new boundary (7,14).

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

You keep repeating this bisection until you are "close enough" to the answer, for example you have a number square of which is within 14-0.01 and 14+0.01 - then you declare that as the answer.

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

OK, that much hint should be good enough for HW. Don't forget to cite StackOverflow.

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

回答by Jim

I see two important computing concepts in your question. The first is binary search, the second is recursion. Since this is homework, here is a contribution towards understanding a binary search, recursion and how to think about them.

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

Think of binary search as dividing the solution "space" in half, keeping the half the solution is in and doing that in succession so that the process converges on the solution. The key concepts for doing this are that you need to engineer a solution "space" that has the following properties:

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

1) can be subdivided, usually in half or at least two pieces

1) 可以细分，通常分成两半或至少两片

2) of the two pieces after subdivision, there is a way to determine which half has the solution so that the process can be repeated on only one half.

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

Recursion involves a function (method in O-O speak) invoking itself. Recursion works really well for a process that converges to a conclusion. It either recurses forever or until you run out of some resource, usually memory, and it fatally stops. The two key concepts for recursion are:

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

1) convergence through some invariance (more on invariance below).

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

2) termination condition (one that recognizes sufficient convergence).

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

Now, for your square root routine. The requirements for the routine are:

现在，对于您的平方根例程。对例程的要求是：

1) Integer input.

1) 整数输入。

2) Integer square-root approximation that gives the floor integer closest to the actual square root.

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

3) Use recursion.

3) 使用递归。

4) Use binary search.

4) 使用二分查找。

It helps to know some mathematics about square roots for this. Elementary calculus and analytical geometry concepts are helpful too. Lets do some reasoning.

为此，了解一些有关平方根的数学会有所帮助。初等微积分和解析几何概念也很有帮助。让我们做一些推理。

We have an arbitrary positive integer x. We want its root y. If we choose some test value for y, we can see if it is the root of x if y * y = x. If y is too big, y * y > x. if y is too small, y * y < x. We also know that 0 <= root <= x and that square-roots of 0 and 1 are trivially zero and 1. Since we are looking for largest integer where y * y <= x (i.e. a floor value) we'll have to account for that too.

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

Here is some mathematical reasoning to help. We know that x = y * y where y is the square root of x. That means: y = x/y.

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

Hmmm... what happens if y is to large to be the square root of x? Then: x < y * y and: x/y < y which means x/y is also too small to be the square root of x. So we know that, for y too large, x/y < square-root of x < y. So, lets find a new y, say y1, between x/y and y as a new test value. The average of x/y and y will do. y1 = (x/y0 + y0)/2 will give a y1 that is closer to the square root of x than y0 if y0 is too large.

嗯...如果 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。

Does this converge? Well, in mathematics using positive real numbers, the average will always be above the value but getting closer each iteration. This satisfies the condition that we successively divide the solution "space" into two parts and know which of the two to keep. In this case, we successively calculate new values below previous ones and below which the answer still lies, allowing us to discard all values above the new one. We stop when we reach a condition where no more new values above the answer exist. Using computers, however, results in binary approximations of real numbers. With integers, there is truncation in division. This may affect the convergence beneficially or adversely. In addition, your answer is supposed to be the largest integer smaller than or equal to the square root. It's wise to take a look at the kind of convergence we will get.

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

Because of integer division turncation, y1 = (x/y0 + y0)/2 will converge until successive iterations reach an integer root or a floor value for (i.e. the largest integer less than) the root. This is ideal. If we start with a proposed value for the root that has to be larger than the root, say x itself, the first value for yn where yn * yn <= x is the desired result.

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

The simple answer is that, when we start with y0 > y, the first new yn that is less than or equal to y, then y - yn < 1. That is, yn is now the floor value for which we've been looking and we now have a termination condition that exactly satisfies the conditions for the required answer.

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

Here are basic iterative and recursive solutions. The solutions don't incude safety features to ensure negative values are not input for x. The one major concern is to avoid dividing by zero in case someone wants to find the square root of 0. Since that is a trivial answer, both the recursive and iterative methods return 0 before division by zero can take place. Both the recursive and iterative solutions work with the trivial cases for finding the square roots of 0 and of 1.

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

There is another analysis that always has to be done with int and long arithmetic in Java. A major concern is integer overflow since Java does nothing about int or long overflow. Overflow results in twos-complement values (look that up elsewhere) that can lead to bogus results and Java does not throw exceptions with int or long overflow.

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

In this case, it is easy to avoid arithmetic that could result in an internal overflow with large values of x. If we create a termination condition such as y0 * y0 < x we risk overflow if x is greater than the square root of Integer.MAX_VALUE since y0 * y0, an intermediate value, will immediately exceed the maximum int value. However, we can rearrange the termination condition to y0 < x / y0. We still have a problem with the calculations: ((x / y0) + y0) / 2) if x and y0 are Integer.MAX_VALUE since it wll attempt Integer.MAX_VALUE + 1. However, we can always start with a value less than x that is guaranteed to be > y. x / 2 works for all values of x > 1. Since the square root of x where x is either 0 or 1 is simply x, we can easily test for those values and simply return the correct and trivial value. You can construct code to prevent using values < 0 or values > Integer.MAX_VALUE. The same can be applied if we use long instead of int. Welcome to computing in the real world!

在这种情况下，很容易避免可能导致 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

You can test the recursive solution to find out how many instances will result on the frame stack, but you will see that it converges very fast. It's interesting to see that the iterative solution is much smaller and faster than the recursive one, something that is often not the case and is why recursion gets used where it can be predicted that stack resources are sufficient for the recursion depth.

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

回答by edst

Iterative binary solution:

迭代二进制解决方案：

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

回答by bwidtmann

edst solution is good, but there is a mistake in line 11:

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

mid = (high - low) / 2;

should be

应该

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

回答by fikry

You can use this java method (Iterative)

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

You can drive your own recursive method

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

回答by learner

Here is the recursive solution in Java using binary search :

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

    }
}