Trusted answers to developer questions

How to find the square root of an integer using binary search

Get Started With Data Science

Learn the fundamentals of Data Science with this free course. Future-proof your career by adding Data Science skills to your toolkit — or prepare to land a job in AI, Machine Learning, or Data Analysis.

Problem

Given a positive integer (N), find the square root of the number using binary search.

Algorithm

Below are the steps to find the square root of an integer (N) using binary search.

Step 1: Let Left = 1, and Right = N.

Step 2: Loop until Left <= Right

Step 2.1: Middle = (Left + Right ) / 2, Square = Middle * Middle.

Step 2.2: If (Square == N), return Middle as the answer.

Step 2.3: If (Square < N), then Left = Middle + 1, go to Step 1.

Step 2.4: Else Right = Middle - 1 (as Square > N)

Step 2.5: Go to Step 1.

Step 3: Return NOT_A_PERFECT_SQUARE (which in this case would be a -1 because the function has to return an integer).

Take a look at the code below to understand this better.

Code

In our code, we utilize BigInteger class to store large squared numbers that overflow if we use int data type.

import java.math.BigInteger;
class SquareRoot {
public static final BigInteger NOT_A_PERFECT_SQUARE = new BigInteger("-1");
public static BigInteger squareRoot(long n){
/*Base condition when n=0 because for this case, left would
be greater than the right and sqaure root wouldn't be computed
for 0 and -1 will b returned.*/
if (n==0)
{
return BigInteger.valueOf(0);
}
// For n > 0
BigInteger left = new BigInteger("1");
BigInteger right = BigInteger.valueOf(n);
BigInteger middle = new BigInteger("1");
while((left.compareTo(right)) == 0 || (left.compareTo(right)) == -1) {
middle = (left.add(right)).divide(BigInteger.valueOf(2));
BigInteger square = middle.multiply(middle);
int check1 = square.compareTo(BigInteger.valueOf(n));
if (check1==0) {
return middle;
}
if (check1 == -1) {
left = middle.add(BigInteger.valueOf(1));
} else {
right = middle.subtract(BigInteger.valueOf(1));
}
}
return NOT_A_PERFECT_SQUARE;
}
public static void main( String args[] ) {
System.out.println( "Square root of 24 : " + squareRoot(24));
System.out.println( "Square root of 1: " + squareRoot(1));
System.out.println( "Square root of 4: " + squareRoot(4));
System.out.println( "Square root of 9: " + squareRoot(9));
System.out.println( "Square root of 16: " + squareRoot(16));
System.out.println( "Square root of 25: " + squareRoot(25));
System.out.println( "Square root of 36: " + squareRoot(36));
System.out.println( "Square root of 49: " + squareRoot(49));
System.out.println( "Square root of 64: " + squareRoot(64));
System.out.println( "Square root of 81: " + squareRoot(81));
System.out.println( "Square root of 100: " + squareRoot(100));
}
}

Conclusion

The time complexity of this algorithm is O(log(N)), logarithmic time. Here, N is the number for which the square root is to be computed. The space complexity of the solution is O(log(1), constant space. This is because we don’t need any additional storage other than local variables like left, right, middle, and square.

RELATED TAGS

sqrt
java
binary search
square root
Did you find this helpful?