# Square Root using Binary Search Probelm: Given a number, we need to find the square root of it (floor of its square root)

Examples:

``````Input: x = 4
Output: 2``````

Solution:

``````/**
* <p><b>Square Root: </b> is to find square root (floor of the
* square root) for a given number.</p>
* <p><b>Time Complexity:</b> O(log x)</p>, x is given number
* <p><b>Usage:</b></p>
* {@code
* SquareRoot.of(25);
* }
*/
public class SquareRoot {

/**
* <b>Flow:</b>
* <p>Make use of Binary Search Algorithm</p>
* <p>Consider a range from 1.....x
*     <ul>
*         <li>We check if x/2 is a square root, by (x/2 * x/2 == x),
*         if so return x/2</li>
*         <li>if it is more than x, we check in left half, high = mid - 1</li>
*         <li>else, check in right half, low = mid + 1, we store mid as
*     </ul>
* </p>
* @param x given number
* @return square root of given number
*/
public static double of(double x) {
double low = 1, high = x, result = -1;

while (low <= high) {
long mid = (long) ((low + high) / 2);
double mSq = mid * mid;

if (mSq == x)
return mid;
else if (mSq > x)
high = mid - 1;
else {
low = mid + 1;
result = mid;
}
}
return result;
}
}``````

Time Complexity: O(log x), Auxiliary Space: O(1)