Compute and return the square root of a non-negative integer number.
The decimal digits are shortened, and only the integer component of the result is returned because the return type is an integer.
num = 8
2
num = 4
2
We can use binary search to solve this problem.
The intuition behind the solution is that the square root of the number lies in the range [2, num / 2]
. So, we can consider the range to be an array of numbers and search for the integer part of the square root of the number.
The steps of the algorithm are as follows:
Initialize start=2
and end=num/2
.
Until start <= end
, do the following:
start + (end - start) / 2
.mid * mid
and store it in a variable midSqr
.midSqr
is greater than num
, it means the result lies in the left part of the array, i.e., from start
to mid-1
.midSqr
is lesser than num
, it means the result lies in the right part of the array, i.e., from mid+1
to end
.midSqr
is equal to num
, it means we have found the result.When end > start
, the loop finishes, and the end
will be the result.
O(log (num))
O(1)
Look at the following illustration for a better understanding of the algorithm.
import java.util.*;public class Main{private static int sqrt(int num){int start = 2, end = num / 2;while(start <= end){int mid = start + (end - start) / 2;long midSqr = (long) mid * mid;if(midSqr > num) end = mid - 1;else if(midSqr < num) start = mid + 1;else return mid;}return end;}public static void main( String args[] ) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();System.out.printf("Sqrt(%s) = %s", num, sqrt(num));}}
Enter the input below