Raíz cuadrada del piso sin usar la función sqrt(): recursiva

Dado un número N , la tarea es encontrar la raíz cuadrada del piso del número N sin usar la función de raíz cuadrada incorporada. La raíz cuadrada mínima de un número es el mayor número entero que es menor o igual que su raíz cuadrada.

Ejemplos:  

Entrada: N = 25 
Salida: 5 
Explicación: 
Raíz cuadrada de 25 = 5. Por lo tanto, 5 es el mayor número entero menor que igual a la raíz cuadrada de 25. 

Entrada: N = 30 
Salida: 5 
Explicación: 
Raíz cuadrada de 30 = 5,47 
Por lo tanto, 5 es el mayor número entero menor que igual a Raíz cuadrada de 30 (5,47) 
 

Enfoque ingenuo: 
en el enfoque básico para encontrar la raíz cuadrada del piso de un número, encuentre el cuadrado de los números de 1 a N , hasta que el cuadrado de algún númeroK sea mayor que N. Por lo tanto, el valor de (K – 1) será la raíz cuadrada mínima de N.

A continuación se muestra el algoritmo para resolver este problema utilizando el enfoque Naive: 

• Iterar un ciclo desde los números 1 a N en K.
• Para cualquier K, si su cuadrado se vuelve mayor que N, entonces K-1 es la raíz cuadrada mínima de N.

Complejidad de tiempo: O(√N)

Enfoque eficiente: 
desde el enfoque Naive, está claro que la raíz cuadrada mínima de N estará en el rango [1, N]. Por lo tanto, en lugar de verificar cada número en este rango, podemos buscar de manera eficiente el número requerido en este rango . Por lo tanto, la idea es usar la búsqueda binaria para encontrar eficientemente la raíz cuadrada del piso del número N en log N.

A continuación se muestra el algoritmo recursivo para resolver el problema anterior mediante la búsqueda binaria: 

• Implemente la búsqueda binaria en el rango de 0 a N.
• Encuentre el valor medio del rango usando la fórmula:

mid = (start + end) / 2

• Caso base: la llamada recursiva se ejecutará hasta que el cuadrado de mid sea menor o igual a N y el cuadrado de (mid+1) sea mayor que igual a N.

(mid2 ≤ N) and ((mid + 1)2 > N)

• Si el caso base no se cumple, el rango se cambiará en consecuencia. 
  • Si el cuadrado de mid es menor que igual a N, entonces el rango se actualiza a [mid + 1, end]

if(mid2 ≤ N)
    updated range = [mid + 1, end]

• Si el cuadrado de mid es mayor que N, entonces el rango se actualiza a [low, mid + 1]

if(mid2 > N)
    updated range = [low, mid - 1]

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation to find the
// square root of the number N
// without using sqrt() function
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the square
// root of the number N using BS
int sqrtSearch(int low, int high, int N)
{
 
    // If the range is still valid
    if (low <= high) {
 
        // Find the mid-value of the range
        int mid = (low + high) / 2;
 
        // Base Case
        if ((mid * mid <= N)
            && ((mid + 1) * (mid + 1) > N)) {
            return mid;
        }
 
        // Condition to check if the
        // left search space is useless
        else if (mid * mid < N) {
            return sqrtSearch(mid + 1, high, N);
        }
        else {
            return sqrtSearch(low, mid - 1, N);
        }
    }
    return low;
}
 
// Driver Code
int main()
{
    int N = 25;
    cout << sqrtSearch(0, N, N)
         << endl;
    return 0;
}

// Java implementation to find the
// square root of the number N
// without using sqrt() function
class GFG {
     
    // Function to find the square
    // root of the number N using BS
    static int sqrtSearch(int low, int high, int N)
    {
     
        // If the range is still valid
        if (low <= high) {
     
            // Find the mid-value of the range
            int mid = (int)(low + high) / 2;
     
            // Base Case
            if ((mid * mid <= N)
                && ((mid + 1) * (mid + 1) > N)) {
                return mid;
            }
     
            // Condition to check if the
            // left search space is useless
            else if (mid * mid < N) {
                return sqrtSearch(mid + 1, high, N);
            }
            else {
                return sqrtSearch(low, mid - 1, N);
            }
        }
        return low;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int N = 25;
        System.out.println(sqrtSearch(0, N, N));
    }
}
 
// This code is contributed by Yash_R

# Python3 implementation to find the
# square root of the number N
# without using sqrt() function
 
# Function to find the square
# root of the number N using BS
def sqrtSearch(low, high, N) :
 
    # If the range is still valid
    if (low <= high) :
 
        # Find the mid-value of the range
        mid = (low + high) // 2;
 
        # Base Case
        if ((mid * mid <= N) and ((mid + 1) * (mid + 1) > N)) :
            return mid;
 
        # Condition to check if the
        # left search space is useless
        elif (mid * mid < N) :
            return sqrtSearch(mid + 1, high, N);
     
        else :
            return sqrtSearch(low, mid - 1, N);
 
    return low;
 
# Driver Code
if __name__ == "__main__" :
 
    N = 25;
    print(sqrtSearch(0, N, N))
 
# This code is contributed by Yash_R

// C# implementation to find the
// square root of the number N
// without using sqrt() function
using System;
 
class GFG {
      
    // Function to find the square
    // root of the number N using BS
    static int sqrtSearch(int low, int high, int N)
    {
      
        // If the range is still valid
        if (low <= high) {
      
            // Find the mid-value of the range
            int mid = (int)(low + high) / 2;
      
            // Base Case
            if ((mid * mid <= N)
                && ((mid + 1) * (mid + 1) > N)) {
                return mid;
            }
      
            // Condition to check if the
            // left search space is useless
            else if (mid * mid < N) {
                return sqrtSearch(mid + 1, high, N);
            }
            else {
                return sqrtSearch(low, mid - 1, N);
            }
        }
        return low;
    }
      
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 25;
        Console.WriteLine(sqrtSearch(0, N, N));
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation to find the
// square root of the number N
// without using sqrt() function
 
// Function to find the square
// root of the number N using BS
function sqrtSearch(low, high, N)
{
     
    // If the range is still valid
    if (low <= high)
    {
         
        // Find the mid-value of the range
        var mid = parseInt( (low + high) / 2);
 
        // Base Case
        if ((mid * mid <= N) &&
           ((mid + 1) * (mid + 1) > N))
        {
            return mid;
        }
 
        // Condition to check if the
        // left search space is useless
        else if (mid * mid < N)
        {
            return sqrtSearch(mid + 1, high, N);
        }
        else
        {
            return sqrtSearch(low, mid - 1, N);
        }
    }
    return low;
}
 
// Driver Code
var N = 25;
 
document.write(sqrtSearch(0, N, N));
 
// This code is contributed by todaysgaurav
 
</script>

5

Análisis de rendimiento: 

• Complejidad de tiempo: como en el enfoque anterior, se usa una búsqueda binaria en el espacio de búsqueda de 0 a N que toma el tiempo O (log N) en el peor de los casos, por lo tanto, la complejidad de tiempo será O (log N) .
• Complejidad espacial: como en el enfoque anterior, teniendo en cuenta el espacio de pila utilizado en las llamadas recursivas que pueden tomar espacio O (logN) en el peor de los casos, por lo tanto, la complejidad espacial será O (log N)