Programa Java para encontrar la raíz cuadrada de un número usando la búsqueda binaria

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

Ejemplos:

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.

Enfoque ingenuo:

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

// Java program to Find the square root of given numbers
// by brute force technique
  
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 <= 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);
    }
}

4

Complejidad espacial: O(1)

Complejidad de tiempo: O(n)

Enfoque eficiente (búsqueda binaria): la búsqueda binaria utilizó el enfoque Divide and Conquer que hace que la complejidad sea O (logn).

Algoritmo:

• Inicializar izquierda = 0 y derecha = n
• Calcular mid=left+(right-left)/2
• Si mid*mid es igual al número devuelve el mid.
• Si mid*mid es menor que el número, almacene el mid en ans ya que posiblemente esta sea la respuesta y aumente left=mid+1 y ahora verifique en la mitad derecha.
• Si mid*mid es mayor que el número y disminuye right=mid-1 ya que el valor esperado es menor, ahora miraremos la mitad izquierda o escanearemos los valores más pequeños.
• devolver la respuesta

Implementación:

// Java program to Find the square root of given numbers
// using Binary search
  
// Importing libraries
import 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));
    }
}

3

Complejidad de tiempo: O (logn)