Binary Search to Compute Square root (Java)

Question

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

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

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

lowlow <= n < highhigh

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