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

binary-search java recursion square-root

2022-09-04 05:03:15

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

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

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

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

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

如果您了解此代码，则编写递归版本应该很简单。

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

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

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

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