Given a non-negative number find the cube root of a number using the binary search approach.
Examples :
Input: x = 27 Output: 3 Explanation: The cube root of 16 is 4. Input: x = 120 Output: 4 Explanation: The cube root of 120 lies in between 4 and 5 so floor of the cube root is 4.
Naive Approach:
- Check the cube of every element till n and store the answer till the cube is smaller or equal to the n
Java
// Java Program to Find the cube root// of given number using Naive approachimport 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 * i <= n) {                ans = i;            }        }        return ans;    }    public static void main(String[] args)    {        // Number        int number = 27;        // Checking number        int cuberoot = cuberoot(number);        System.out.println(cuberoot);    }} |
Output
3
Complexity:
SpaceComplexity: O(1) TimeComplexity: O(n)
Efficient Approach (Binary Search):Â
Binary Search used Divide and Conquer approach that makes the complexity is O(log n).
Algorithm:
- Initialize left=0 and right =n
- Calculate mid=left+(right-left)/2
- If mid*mid*mid is equal to the number  return the mid
- If mid*mid*mid is less than the number store the mid in ans and increase left=mid+1
- If mid*mid*mid is more than the number and decrease the right=mid-1
- Return the answer
Implementation:
Java
// Java Program to Find the cube root// of given number using Binary Searchimport java.io.*;import java.util.*;class GFG {    // Function to find cuberoot    static int cuberoot(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 * mid == number) {                return mid;            }              // Shift the lower bound            if (mid * 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 = 215;        System.out.println(cuberoot(number));    }} |
Output
5
Complexity:
SpaceComplexity: O(1) TimeComplexity: O(log n)
