# 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.

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 ≤ 107

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:

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..