Dado un número positivo n y una precisión p, encuentre la raíz cuadrada del número hasta p lugares decimales usando la búsqueda binaria.
Nota: Requisito previo: Búsqueda binaria
Ejemplos:
Input : number = 50, precision = 3 Output : 7.071 Input : number = 10, precision = 4 Output : 3.1622
Hemos discutido cómo calcular el valor integral de la raíz cuadrada en Raíz cuadrada utilizando el enfoque de búsqueda binaria : 1) Como la raíz cuadrada del número se encuentra en el rango 0 <= raíz cuadrada <= número, por lo tanto, inicialice inicio y fin como: inicio = 0 , fin = número. 2) Compara el cuadrado del entero medio con el número dado. Si es igual al número, se encuentra la raíz cuadrada. De lo contrario, busque lo mismo en el lado izquierdo o derecho según el escenario. 3) Una vez que hayamos terminado de encontrar una parte integral, comience a calcular la parte fraccionaria. 4) Inicialice la variable de incremento en 0.1 y calcule iterativamente la parte fraccionaria hasta P lugares. Para cada iteración, el incremento
cambia a 1/10 de su valor anterior.
5) Finalmente devolver la respuesta calculada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// square root of given number
// upto given precision using
// binary search.
#include <bits/stdc++.h>
using namespace std;
// Function to find square root
// of given number upto given
// precision
float squareRoot(int number, int precision)
{
int start = 0, end = number;
int mid;
// variable to store the answer
float ans;
// for computing integral part
// of square root of number
while (start <= end) {
mid = (start + end) / 2;
if (mid * mid == number) {
ans = mid;
break;
}
// incrementing start if integral
// part lies on right side of the mid
if (mid * mid < number) {
start = mid + 1;
ans = mid;
}
// decrementing end if integral part
// lies on the left side of the mid
else {
end = mid - 1;
}
}
// For computing the fractional part
// of square root upto given precision
float increment = 0.1;
for (int i = 0; i < precision; i++) {
while (ans * ans <= number) {
ans += increment;
}
// loop terminates when ans * ans > number
ans = ans - increment;
increment = increment / 10;
}
return ans;
}
// Driver code
int main()
{
// Function calling
cout << squareRoot(50, 3) << endl;
// Function calling
cout << squareRoot(10, 4) << endl;
return 0;
}
Java
// Java implementation to find
// square root of given number
// upto given precision using
// binary search.
import java.io.*;
class GFG {
// Function to find square root
// of given number upto given
// precision
static float squareRoot(int number, int precision)
{
int start = 0, end = number;
int mid;
// variable to store the answer
double ans = 0.0;
// for computing integral part
// of square root of number
while (start <= end) {
mid = (start + end) / 2;
if (mid * mid == number) {
ans = mid;
break;
}
// incrementing start if integral
// part lies on right side of the mid
if (mid * mid < number) {
start = mid + 1;
ans = mid;
}
// decrementing end if integral part
// lies on the left side of the mid
else {
end = mid - 1;
}
}
// For computing the fractional part
// of square root upto given precision
double increment = 0.1;
for (int i = 0; i < precision; i++) {
while (ans * ans <= number) {
ans += increment;
}
// loop terminates when ans * ans > number
ans = ans - increment;
increment = increment / 10;
}
return (float)ans;
}
// Driver code
public static void main(String[] args)
{
// Function calling
System.out.println(squareRoot(50, 3));
// Function calling
System.out.println(squareRoot(10, 4));
}
}
// This code is contributed by vt_m.
Python3
# Python3 implementation to find # square root of given number # upto given precision using # binary search. # Function to find square root of # given number upto given precision def squareRoot(number, precision): start = 0 end, ans = number, 1 # For computing integral part # of square root of number while (start <= end): mid = int((start + end) / 2) if (mid * mid == number): ans = mid break # incrementing start if integral # part lies on right side of the mid if (mid * mid < number): start = mid + 1 ans = mid # decrementing end if integral part # lies on the left side of the mid else: end = mid - 1 # For computing the fractional part # of square root upto given precision increment = 0.1 for i in range(0, precision): while (ans * ans <= number): ans += increment # loop terminates when ans * ans > number ans = ans - increment increment = increment / 10 return ans # Driver code print(round(squareRoot(50, 3), 4)) print(round(squareRoot(10, 4), 4)) # This code is contributed by Smitha Dinesh Semwal.
C#
// C# implementation to find
// square root of given number
// upto given precision using
// binary search.
using System;
class GFG {
// Function to find square root
// of given number upto given
// precision
static float squareRoot(int number, int precision)
{
int start = 0, end = number;
int mid;
// variable to store the answer
double ans = 0.0;
// for computing integral part
// of square root of number
while (start <= end) {
mid = (start + end) / 2;
if (mid * mid == number) {
ans = mid;
break;
}
// incrementing start if integral
// part lies on right side of the mid
if (mid * mid < number) {
start = mid + 1;
ans = mid;
}
// decrementing end if integral part
// lies on the left side of the mid
else {
end = mid - 1;
}
}
// For computing the fractional part
// of square root upto given precision
double increment = 0.1;
for (int i = 0; i < precision; i++) {
while (ans * ans <= number) {
ans += increment;
}
// loop terminates when ans * ans > number
ans = ans - increment;
increment = increment / 10;
}
return (float)ans;
}
// Driver code
public static void Main()
{
// Function calling
Console.WriteLine(squareRoot(50, 3));
// Function calling
Console.WriteLine(squareRoot(10, 4));
}
}
// This code is contributed by Sheharaz Sheikh
PHP
<?php
// PHP implementation to find
// square root of given number
// upto given precision using
// binary search.
// Function to find square root
// of given number upto given
// precision
function squareRoot($number, $precision)
{
$start=0;
$end=$number;
$mid;
// variable to store
// the answer
$ans;
// for computing integral part
// of square root of number
while ($start <= $end)
{
$mid = ($start + $end) / 2;
if ($mid * $mid == $number)
{
$ans = $mid;
break;
}
// incrementing start if integral
// part lies on right side of the mid
if ($mid * $mid < $number)
{
$start = $mid + 1;
$ans = $mid;
}
// decrementing end if integral part
// lies on the left side of the mid
else
{
$end = $mid - 1;
}
}
// For computing the fractional part
// of square root upto given precision
$increment = 0.1;
for ($i = 0; $i < $precision; $i++)
{
while ($ans * $ans <= $number)
{
$ans += $increment;
}
// loop terminates when
// ans * ans > number
$ans = $ans - $increment;
$increment = $increment / 10;
}
return $ans;
}
// Driver code
// Function calling
echo squareRoot(50, 3),"\n";
// Function calling
echo squareRoot(10, 4),"\n";
// This code is contributed by ajit.
?>
Javascript
<script>
// JavaScript program implementation to find
// square root of given number
// upto given precision using
// binary search.
// Function to find square root
// of given number upto given
// precision
function squareRoot(number, precision)
{
let start = 0, end = number;
let mid;
// variable to store the answer
let ans = 0.0;
// for computing integral part
// of square root of number
while (start <= end)
{
mid = (start + end) / 2;
if (mid * mid == number)
{
ans = mid;
break;
}
// incrementing start if integral
// part lies on right side of the mid
if (mid * mid < number) {
start = mid + 1;
ans = mid;
}
// decrementing end if integral part
// lies on the left side of the mid
else {
end = mid - 1;
}
}
// For computing the fractional part
// of square root upto given precision
let increment = 0.1;
for (let i = 0; i < precision; i++) {
while (ans * ans <= number) {
ans += increment;
}
// loop terminates when ans * ans > number
ans = ans - increment;
increment = increment / 10;
}
return ans;
}
// Driver code
// Function calling
document.write(squareRoot(50, 3) + "<br/>");
// Function calling
document.write(squareRoot(10, 4) + "<br/>");
</script>
Producción:
7.071 3.1622
Complejidad del tiempo: El tiempo requerido para calcular la parte integral es O(log(número)) y constante, es decir, = precisión para calcular la parte fraccionaria. Por lo tanto, la complejidad total del tiempo es O(log(número) + precisión) que es aproximadamente igual a O(log(número)).
Publicación traducida automáticamente
Artículo escrito por Sahil_Bansall y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA