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

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 ~= sqrt(250,000)
C = sqrt(250,000) / 250,000
C = 500 / 250,000
C = 1 / 500

Answer 2

Ok, now that it is tagged like homework, 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).

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.

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

Answer 3

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:

low*low <= n < high*high

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