Objective Use binary search to find the square root of a number. Description Cre
ID: 664458 • Letter: O
Question
Objective
Use binary search to find the square root of a number.
Description
Create a class called BinarySearchSqrt with the following methods:
sqrt - A helper method that will call the recursive method for binary search.params
num - The (double) number to find the square root of.
return - The square root of the number given, or -1 if the input is invalid
sqrt - A recursive method that implements binary search to find the square root. This should print out the current best approximation at each step.params
num - the (double) number to find the square root of.
current - The current best approximation of the square root.
low - The current lower bound for the square root.
high - The current upper bound for the square root.
return - The square root of num
In addition, your main method should loop over the user's input, accepting any positive floating point number until the user enters exit (or anything that is invalid).
Since you are comparing doubles, you should use a TOLERANCE of .00001
Example Dialog
Explanation / Answer
public class BinarySearchSqrt {
public static void main(String args[]) {
System.out.println("Square Root of 25 is: " + sqrt(25));
System.out.println("Square Root of 81 is: " + sqrt(81));
System.out.println("Square Root of -100 is: " + sqrt(-100));
System.out.println("Square Root of 1 is: " + sqrt(1));
System.out.println("Square Root of 0 is: " + sqrt(0));
}
/**
* This method use binary search to find the square root.
*
* @param num
* @return square root of the num
*/
private static double sqrt(double num) {
double sqrt = 0;
double low = 0;
double high = num;
double precision = 0.00001;
if (num < 0) {
sqrt = -1;
} else if (num == 0 || num == 1) {
sqrt = num;
} else {
// we will use binary search to narrow down.
while (high - low > precision) {
double current = (low + high) / 2;
sqrt = current * current;
if (sqrt == num) {
return sqrt;
} else if (sqrt > num) {
high = current;
} else {
low = current;
}
}
// if a match is not found
sqrt = (low + high) / 2;
}
return sqrt;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.