Programa Java para encontrar la raíz cúbica de un número dado mediante la búsqueda binaria

Dado un número no negativo, encuentre la raíz cúbica de un número utilizando el enfoque de búsqueda binaria .

Ejemplos:

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.

Enfoque ingenuo:

• Comprueba el cubo de cada elemento hasta n y almacena la respuesta hasta que el cubo sea menor o igual a n

// 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);
    }
}

3

Complejidad:

SpaceComplexity: O(1)
TimeComplexity: O(n)

Enfoque eficiente (búsqueda binaria): 

La búsqueda binaria utilizó el enfoque Divide and Conquer que hace que la complejidad sea O (log n).

Algoritmo:

• Inicializar izquierda = 0 y derecha = n
• Calcular mid=left+(right-left)/2
• Si mid*mid*mid es igual al número devuelve el mid
• Si mid*mid*mid es menor que el número, almacene mid en ans y aumente left=mid+1
• Si mid*mid*mid es mayor que el número y disminuye la derecha = mid-1
• devolver la respuesta

Implementación:

// 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));
    }
}

5

Complejidad:

SpaceComplexity: O(1)
TimeComplexity: O(log n)