Square Root using Binary Search
Srivastava Bodakunti
0
39
Probelm: Given a number, we need to find the square root of it (floor of its square root)
Examples:
Input: x = 4
Output: 2Solution:
/**
* <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
* our current answer</li>
* </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)
