二进制搜索以计算平方根(Java) [英] Binary Search to Compute Square root (Java)

问题描述

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

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

推荐答案

Teh编码:

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:

低低< = n<高高

lowlow <= n < highhigh

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

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

这篇关于二进制搜索以计算平方根(Java)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！