Given a non-negative number find the square root of a number using the binary search approach.
Examples :
Input: x = 16 Output: 4 Explanation: The square root of 16 is 4. Input: x = 5 Output: 2 Explanation: The square root of 5 lies in between 2 and 3 so floor of the square root is 2.
Naive Approach:
- Check the square of every element till n and store the answer till the square is smaller or equal to the n
Java
// Java program to Find the square root of given numbers// by brute force techniqueimport java.io.*;class GFG { static int cuberoot(int n) { int ans = 0; for (int i = 1; i <= n; ++i) { // checking every number cube if (i * i <= n) { ans = i; } } return ans; } public static void main(String[] args) { // Number int number = 16; // Checking number int cuberoot = cuberoot(number); System.out.println(cuberoot); }} |
Output
4
SpaceComplexity: O(1)
TimeComplexity: O(n)
Efficient Approach (Binary Search): Binary Search used Divide and Conquer approach that makes the complexity is O(logn).
Algorithm:
- Initialize left=0 and right =n
- Calculate mid=left+(right-left)/2
- If mid*mid is equal to the number return the mid.
- If mid*mid is less than the number store the mid in ans since this can possibly be the answer and increase left=mid+1 and now check in the right half.
- If mid*mid is more than the number and decrease the right=mid-1 since the expected value is lesser therefore we will now look into the left half part or will be scanning the smaller values.
- Return the answer
Implementation:
Java
// Java program to Find the square root of given numbers// using Binary search// Importing librariesimport java.io.*;import java.util.*;class GFG { // Function to find cuberoot static int squareeroot(int number) { // Lower bound int left = 1; // Upper bound int right = number; int ans = 0; while (left <= right) { // Finding the mid value int mid = left + (right - left) / 2; // Checking the mid value if (mid * mid == number) { return mid; } // Shift the lower bound if (mid * mid < number) { left = mid + 1; ans = mid; } // Shift the upper bound else { right = mid - 1; } } // Return the ans return ans; } public static void main(String[] args) { int number = 15; System.out.println(squareroot(number)); }} |
Output
3
Time Complexity: O(logn)
Auxiliary space: O(1) as it is using constant variables
