Given a positive integer (N), find the square root of the number using binary search.
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.
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 wouldbe greater than the right and sqaure root wouldn't be computedfor 0 and -1 will b returned.*/if (n==0){return BigInteger.valueOf(0);}// For n > 0BigInteger 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));}}
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
.