Finding Square Root Of A Double Number In Java Using Binary Search

The following program uses binary search to effectively find the square root of the number. Given a number, we start dividing it into half and see if the mid value multiplied to itself constitutes the original number (i.e. originalNumber = midValue * midValue). If the square of the midValue is greater than the originalNumber, we start looking into the left half of the number, if it is smaller, we start looking into the right half.

Since we are allowing double numbers as parameter, we are using a double precision to compare.

If the binary search does not exactly find the number, the approximated value of the square root of the half of last known start and end.

package com.icodejava.blog;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 11, 2014
 * Last Modified On - Mar 11, 2014
 */
public class SquareRootFinder {

	public static void main(String args[]) {

		System.out.println("Square Root of 25 is: " + squareRoot(25));
		System.out.println("Square Root of 81 is: " + squareRoot(81));
		System.out.println("Square Root of -100 is: " + squareRoot(-100));
		System.out.println("Square Root of 1 is: " + squareRoot(1));
		System.out.println("Square Root of 0 is: " + squareRoot(0));

	}

	/**
	 * This method use binary search to find the square root.
	 * 
	 * @param number
	 * @return square root of the number
	 */
	private static double squareRoot(double number) {
		double squareRoot = 0;
		double startValue = 0;
		double endValue = number;
		double precision = 0.00001;

		if (number < 0) {
			squareRoot = -1;
		} else if (number == 0 || number == 1) {
			squareRoot = number;
		} else {

			// we will use binary search to narrow down.
			while (endValue - startValue > precision) {
				double midValue = (startValue + endValue) / 2;
				squareRoot = midValue * midValue;

				if (squareRoot == number) {
					return squareRoot;
				} else if (squareRoot > number) {
					endValue = midValue;
				} else {
					startValue = midValue;
				}
			}

			// if a match is not found
			squareRoot = (startValue + endValue) / 2;

		}
		return squareRoot;
	}

}

Here is the output of running the above program:

Square Root of 25 is: 4.999998211860657
Square Root of 81 is: 8.999999463558197
Square Root of -100 is: -1.0
Square Root of 1 is: 1.0
Square Root of 0 is: 0.0