# Java Program to Find the Cube Root of a Given Number Using Binary Search

Given a non-negative number find the cube root of a number using the binary search approach.

**Examples :**

Attention reader! Don’t stop learning now. Get hold of all the important **Java Foundation** and Collections concepts with the **Fundamentals of Java and Java Collections Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:x = 27Output:3Explanation:The cube root of 16 is 4.Input:x = 120Output: 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 approach` `import` `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 Search` `import` `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)