Square Root Using Binary Search in Java

(Asked in AMAZON, ACCOLITE, FLIPKART, VMWare..etc)

Given an integer x. The task is to find the square root of x. If x is not a perfect square, then return floor(√x).

Input:
First line of input contains number of testcases T. For each testcase, the only line contains the number x.

Output:
For each testcase, print square root of given integer.

Your Task:
The task is to complete the function floorSqrt() which should return the square root of given number x.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ T ≤ 10000
1 ≤ x ≤ 10⁷

Example:
Input:
2
5
4
Output:
2
2

Explanation:
Testcase 1: Since, 5 is not perfect square, so floor of square_root of 5 is 2.
Testcase 2: Since, 4 is a perfect square, so its square root is 2.

Algorithm:

1) Start with ‘start’ = 0, end = ‘x’,
2) Do following while ‘start’ is smaller than or equal to ‘end’.
      a) Compute ‘mid’ as (start + end)/2
      b) compare mid*mid with x.
      c) If x is equal to mid*mid, return mid.
      d) If x is greater, do binary search between mid+1 and end. In this case, we also update ans (Note that we need floor).
      e) If x is smaller, do binary search between start and mid.

Note: I suggest you don’t use any library function to find square root because of time complexity the given solution in O(LogN).

Code:

package searchingSorting;

import java.util.Scanner;

public class SquareRoot {
	
	static long root(long x) {
		long start = 0;
		long end = x;
		
		while(start <= end) {
			long mid = (start + end) / 2;
			
			if((mid * mid) == x)
				return mid;
			
			if((mid * mid) < x)
				start = mid + 1;
			else
				end = mid - 1;
		}
		
		return (long) Math.floor(end);
		
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long x = sc.nextLong();
		
		System.out.println(root(x));
	}

}

Hope you guys understand the above code..

Thanks for reading…!

Thank You..!

Happy Coding…!