Crea una cuenta o inicia sesión

¡Continúa aprendiendo sin ningún costo! Únete y comienza a potenciar tu carrera

Búsqueda Binaria

14/31
Recursos

Aportes 417

Preguntas 49

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

Lo aplicado en esta clase se denomina Métodos Numéricos, el metodo usado en la clase es conocido como método de la bisección, es un tipo de búsqueda incremental en el que el intervalo se divide siempre a la mitad.
Existen diversos métodos que tiene una mejor convergencia para la aproximación a la solución, el mas conocido es el metodo newtoh raphson.

Pueden revisar este libro si les interesa aprender mas sobre Métodos Numéricos
Métodos Numéricos para Ingenieros

Nuevamente largo, pero creo yo que claro jeje
Espero a alguien le sirva

# numero al que se le calculará la raiz cuadrada
objetivo = int(input('Escoge un numero: '))

# margen de error para encontrar esa raiz cuadrada
epsilon = 0.01

# valor minimo para calcular largo del conjunto
bajo = 0.0

# valor maximo para calcular largo de conjunto. Función max() >> elegirá el valor máximo de los parámetros que le demos; colocamos 1.0 como valor mínimo aceptado (así nos cubrimos de que, por ejemplo, el usuario coloque un valor negativo), y objetivo (valor que nos dará el usuario)
alto = max(1.0, objetivo)

# aqui generamos el valor medio de nuestro conjunto, a lo cual se puede genera el condicional (if) para elegir la mitad menor o la mitad mayor.
respuesta = (alto + bajo) / 2

# para entender esto, lo más fácil es imaginar que el while saltará de un grupo de mitades a otro, dependiendo de la situación, hasta que el grupo se divida lo suficiente como para dar con el objetivo.

# el while comienza diciendo que, hasta que la respuesta de con el resultado (con un margen de error de 0.01, es decir epsilon), se hará la iteración del paso 2 de este algoritmo. 
while abs(respuesta**2 - objetivo) >= epsilon:
    # si respuesta**2 no es mayor que objetivo, quiere decir que respuesta debe ser mayor (de respuesta para abajo, no nos sirve; nos sirve el rango de respuesta para arriba). 
    # RECORDAR: respuesta es el valor medio del conjunto que estamos analizando (mirar más arriba)
    if respuesta**2 < objetivo:
        # como sabemos que de respuesta para abajo no tenemos un valor que nos sirva, actualizamos el piso (bajo) de nuestro conjunto a el valor actual de respuesta.
        bajo = respuesta
    # si respuesta**2 es mayor que objetivo, quiere decir que respuesta debe ser menor (de respuesta para arriba, no nos sirve; nos sirve el rango de respuesta para abajo)
    else:
        # como sabemos que respuesta para arriba no tenemos un valor que nos sirva, actualizamos el techo (alto) de nuestro conjunto a el valor actual de respuesta
        alto = respuesta

    # Saliendo del else, ejecutamos el código para que respuesta (punto medio de nuestro conjunto) se actualice al nuevo conjunto.
    respuesta = (alto + bajo) / 2

##################################
# Repitiendo este loop, llegará un punto en el que el conjunto sea muy pequeño, y hallaremos la raiz cuadrada.
# Los loops necesarios serán mucho menos que si usamos busqueda exhaustiva o aproximacion

print(f'La raiz cuadrada de {objetivo} es {respuesta}')

Este algoritmo si le gustó más a mi procesador.

Les comparto este libro https://www.casadellibro.com/libro-metodos-numericos-para-ingenieros/9789701061145/1140185

Hace dos años era profesor de esa materia, conoci platzi buscando una alternativa a matlab y la encontre en python, de hecho este algoritmo viene en uno de los primeros temas, asi como otros metodos, voy a repasar la informacion y espero compartirles algunos slides a manera de tutorial para que los puedan implementar en python, viene paso a paso matematicamente espero hacerlos a manera de tutorial.

Búsqueda Binaria

Cuando la respuesta se encuentra en un conjunto ordenado, podemos utilizar búsqueda binaria. Es altamente eficiente, pues corta el espacio de búsqueda en dos por cada iteración. Los pasos que sigue son:

  1. Consideramos como segmento inicial de búsqueda a la lista completa.
  2. Analizamos el punto medio del segmento (el valor central), si es el valor buscado, devolvemos el índice del punto medio.
  3. Si el valor central es mayor al buscado, podemos descartar el segmento que está desde el punto medio hacia la a derecha.
  4. Si el valor central es menor al buscado, podemos descartar el segmento que está desde el punto medio hacia la izquierda.
  5. Una vez descartado el segmento que no nos interesa, volvemos a analizar el segmento restante, de la misma forma.
  6. Si en algún momento el segmento a analizar tiene longitud 0 o negativa significa que el valor buscado no se encuentra en la lista.

Para verlo de forma gráfica buscaremos el valor 18 en la lista [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23].

Para realizar un ejemplo práctico crearemos un programa para buscar raíces cuadradas.

objetivo = int(input('Escoge un numero: '))

epsilon = 0.01  # Definimos nuestro margen de error.

bajo = 0.0      # Inicializamos la parte baja de nuestra busqueda como 0
alto = max(1.0, objetivo)   # Entre el numero que ingresamos y 1 vamos a tomar el mayor valor.
respuesta = (alto + bajo) / 2   # Definimos la mitad entre bajo y alto.

# Mientras el margen de error sea mayor a epsilon.
while abs(respuesta**2 - objetivo) >= epsilon:

    # Si ((alto+bajo)/2)^2 es menor a nuestro numero objetivo
    if respuesta**2 < objetivo:
        
        # Definimos la parte baja de nuestra busqueda como (alto + bajo)/2
        bajo = respuesta

    # En caso que (alto+bajo)/2 es mayor a nuestro numero objetivo
    else: 
        # Definimos la parte baja de nuestra busqueda como (alto + bajo)/2
        alto = respuesta

    # Luego definimos nuevamente la mitad entre alto y bajo.
    respuesta = (alto + bajo) / 2

# Cuando el ciclo ya alcance un error menor a epsilon imprimiremos el resultado.
print(f'La raiz cuadrada de {objetivo} es {respuesta}')

Este algoritmo es extremadamente rápido en comparación a los anteriores y esto es justamente lo que lo hace uno de los mas potentes.

Se nota en gran medida la pasión del profesor, profes como David son los que denotan la calidad de Platzi.

La busqueda binaria es parecida a cuando tenemos un libro de muchas páginas y queremos encontrar una página en específico sin mirar el índice.

Ejemplo:

  1. Tenemos un libro de 1,000 páginas y queremos encontrar la página 345.
  2. Abrimos el libro por la mitad para partir de un punto de referencia, estando en la página 500 vamos a descartar la mitad superior (de 500 a 1,000)
  3. Con esto sabemos que la página 345 debe estar entre la página 0 y la 500, entonces repetimos la técnia de partir a la mitad la parte del libro en la que estámos buscando.
  4. Así es que se repite hasta encontrar a la página 345.

También les recomiendo que lean este artículo sobre búsqueda binaria:
https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

Código con mejor visualización:

import time

objetivo = int(input('Escoge un numero: '))
epsilon = 0.000001
bajo = 0.0
alto = max(1.0, objetivo)
respuesta = (alto + bajo)/2
num = 0 #numero para contar iteraciones

start = time.time()

while abs(respuesta**2 - objetivo) >= epsilon:

    if respuesta**2 < objetivo:
        bajo = respuesta
    else:
        alto = respuesta
    
    respuesta = (alto + bajo)/2

    num += 1

end = time.time()

print(f'Para resolver hizo {num} iteraciones y se demoro {end - start} segundos')

print(f'La raiz cuadrada de {objetivo} es {respuesta}')

Si lo quieres ver con manzanitas:


How to Do a Binary Search in Python

Entenderlo puede que sea sencillo, pero no importa cuanto te lo expliquen, lo mas importante es lograr hacerlo por sí mismo. Esto realmente es lo complicado.





Escoge un numero: 4
La raiz cuadrada de 4 es 1.9999847412109375
Epsilon:        0.0001
Iteraciones:    16
Inicio:         2020-06-10 22:03:37.193309
Fin:            2020-06-10 22:03:37.193393

Dr. Stranger usando el algoritmo anterior

Usando el nuevo algoritmo 😃

CONSEJO DEL DRTRANGER

para saber que tanto se demora tu código corriendo les recomiendo usar :

import time


tic=time.time()

# aqui va tu código a correr

toc=time.time()

#para ver cuanto tiempo tardó corriendo:
print(' el tiempo que se demoró en correr es:\n ' + str(abs(tic-toc)*1000) + 'milisegundo')

En la linea 4, coloca max(1.0, objetivo). La idea de usar la funcion maximo de esa manera, es que el programa funcione tambien con numeros entre 0 y 1. La razon de esto es que para los numeros de este conjunto, las raices cuadradas son mayor al numero. Matematicamente seria asi:
sqrt(x) >= x para todo x perteneciente al intervalo [0, 1]
Esta opcion no se esta aprovechando, ya que cuando introduce el input del numero usa int(input(…)) cuando deberia usar float(input…).

Increíble. Encontrar la raíz cuadrada de 44: por aproximación de soluciones tomó 6.633.175 iteraciones, mientras que por búsqueda binaria solo tomó 12 iteraciones.

Usé el código de la enumeración y la aproximación para armar un “híbrido”: Primero busca la respuesta por enumeración, si no encuentra la respuesta en el dominio de los enteros continúa la búsqueda por aproximación desde el valor entero donde quedó. Eso reduce enormemente el tiempo de ejecución.
Luego hice un comparativo entre las 4 formas para hallar la raíz de 5. Los resultados estan en la imagen. A pesar de ganar gran velocidad con la aproximación híbrida la búsqueda binaria es a todas luces superior en desempeño.

Recomiendo también imprimir el respuesta**2, esa impresión me ayudo a entenderlo.

Descubrí un comportamiento indeseado en el codigo de David.
Cuando ingresas un numero negativo menor que epsilon negativo (por ejemplo -5) el bucle while itera por siempre, respuesta tomará el valor de 0.5 y cada iteración se dividira sobre 2 lo cual es un problema porque respuesta -> 0, además la condición del bucle se evaluaría así:

if abs(respuesta^2 - (-5)) >= epsilon que es igual a if abs(respuesta^2 + 5) >=epsilon

Como respuesta tenderá a 0 y 5 siempre será mayor a epsilon.

Ahora, si ingresamos un numero negativo mayor que epsilon negativo (por ejemplo -0.001) ahora si ya no habrá iteraciones infinitas, pero obtendremos una afirmación como esta:

"la raiz cuadrada de -0.001 es -0.0316…"
Lo cual esta mal, debería ser 0.0316i (imaginario porque no hay numeros reales que sean raiz de un negativo)
Hagan sus pruebas, ingresen un numero negativo.

¿COMO ARREGLARLO?

Solo hay que agregar una validación para numeros negativos debajo del input:

number = int(input('Give me a number: '))
#validation
if number < 0:
	print('Sorry, we do not work with negative numbers')
	exit()

Miren:

Es interesante, las calculadoras científicas baratas para sacar el resultado de una raíz cuadrada deben usar este algoritmo con un épsilon de 0.000000001 para sacar su resultado

raiz de 87

con el algoritmo de busqueda exhautiva
iteraciones: 93269
rango de tolerancia: 0.01
respuesta: 9.326899999991602

con el algoritmo de busqueda binaria
iteraciones:14
rango de tolerancia: 0.01
respuesta: 9.327117919921875

con el algoritmo de la bisección
iteraciones: 17
rango de tolerancia: 0.0001
respuesta: 9.327375295210857

Entonces habría que aplicar un algoritmo de ordenamiento antes, en otro tipo de escenario. ¿Correcto?

Entiendo lo que es un Binary Search, pero esto de la raíz cuadrada siento que es bastante enredado, de hecho me hubiera gustado más estos temas sin ese ejemplo tan matemático.

También es importante resaltar que no podemos pasarnos de un épsilon de 16 dígitos porque se pasa del limite de decimales en un tipo float

⠄⠄⠄⢰⣧⣼⣯⠄⣸⣠⣶⣶⣦⣾⠄⠄⠄⠄⡀⠄⢀⣿⣿⠄⠄⠄⢸⡇⠄⠄ ⠄⠄⠄⣾⣿⠿⠿⠶⠿⢿⣿⣿⣿⣿⣦⣤⣄⢀⡅⢠⣾⣛⡉⠄⠄⠄⠸⢀⣿⠄ ⠄⠄⢀⡋⣡⣴⣶⣶⡀⠄⠄⠙⢿⣿⣿⣿⣿⣿⣴⣿⣿⣿⢃⣤⣄⣀⣥⣿⣿⠄ ⠄⠄⢸⣇⠻⣿⣿⣿⣧⣀⢀⣠⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⣿⣿⣿⠄ ⠄⢀⢸⣿⣷⣤⣤⣤⣬⣙⣛⢿⣿⣿⣿⣿⣿⣿⡿⣿⣿⡍⠄⠄⢀⣤⣄⠉⠋⣰ ⠄⣼⣖⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⢇⣿⣿⡷⠶⠶⢿⣿⣿⠇⢀⣤ ⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⣿⣿⣿⣿⣿⣿⣷⣶⣥⣴⣿⡗ ⢀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄ ⢸⣿⣦⣌⣛⣻⣿⣿⣧⠙⠛⠛⡭⠅⠒⠦⠭⣭⡻⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠄ ⠘⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠄⠹⠈⢋⣽⣿⣿⣿⣿⣵⣾⠃⠄ ⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⠄⣴⣿⣶⣄⠄⣴⣶⠄⢀⣾⣿⣿⣿⣿⣿⣿⠃⠄⠄ ⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⡄⢻⣿⣿⣿⠄⣿⣿⡀⣾⣿⣿⣿⣿⣛⠛⠁⠄⠄⠄ ⠄⠄⠄⠄⠈⠛⢿⣿⣿⣿⠁⠞⢿⣿⣿⡄⢿⣿⡇⣸⣿⣿⠿⠛⠁⠄⠄⠄⠄⠄ ⠄⠄⠄⠄⠄⠄⠄⠉⠻⣿⣿⣾⣦⡙⠻⣷⣾⣿⠃⠿⠋⠁⠄⠄⠄⠄⠄⢀⣠⣴ ⣿⣿⣿⣶⣶⣮⣥⣒⠲⢮⣝⡿⣿⣿⡆⣿⡿⠃⠄⠄⠄⠄⠄⠄⠄⣠⣴⣿⣿⣿

Intente hacerlo por mi cuenta antes de ver la clase y mi ciclo se ciclaba 😂😂 vi la clase y me di cuenta que me faltaba la función abs 😂💔

¿Alguien noto que se puede buguear si se pone un numero muy alto?

Por ejemplo yo puse 123123123123 y se queda como cargando pero tira lo mismo numero en respuesta, alto y bajo pero si le quitan un numero ya si da el resultado inmediato ejemplo 12312312312

yo recuerdo que hace años, aprendí estos conceptos en la universidad en un curso de análisis numérico, y además recuerdo que hice una presentación para un curso de análisis de algoritmos sobre el método de bisección como aplicación de la búsqueda binaria para encontrar el resultado aproximado de un cálculo matemático, el código lo realicé en lenguaje C XD

Basado en esta clase que estuvo genial, les comparto un algoritmo que adivina un numero del 1 al 1000 en maximo 10 intentos

import math 
bajo = 0
alto = 1000
intentos = 1
respuesta = (alto + bajo) / 2

valorAdivinado = False

while valorAdivinado == False:
    valor = int(input(f'Su valor es mayor a {math.floor(respuesta)} ? \n1.Si \n2.No \n3.Es mi umero\n'))

    if valor == 1:
        bajo = respuesta
    elif valor == 2:
        alto = respuesta
    else:
        valorAdivinado = True
        print(f'Su numero es {math.floor(respuesta)}, se hizo en {intentos} intentos')

    respuesta = (alto + bajo) / 2
    intentos += 1

¿Cuándo usar búsqueda binaria?
Cuando tengo una lista de elementos y cada uno tiene una propiedad de nombre, y para encontrar el que quiero, tengo que revisar toda la lista hasta encontrar el que coincida.

Pero, revisarla toda NO es la forma más eficiente. Ya que, ocasionalmente, el elemento que se está buscando estará al principio de la matriz, y otras veces estará al final. Lo cual, no es un gran problema si la matriz tiene 10 o 20 elementos, pero ¿qué pasa con 1000, 10000 o 1000000?. En estos casos, podemos reducir el tiempo promedio que la computadora dedica a buscar el elemento correcto, si aplicamos una búsqueda binaria.

NOTA IMPORTANTE: Nuestra lista o matriz de elementos debe estar ordenada.

Ser mas inteligente en la formula en como ejecutamos nuestro codigo.

En la Universidad recuerdo un curso llamado Analisis numerico.
Ojala Platzi haga un curso de ello. Creo que es necesario para entender mas a profundidad sobre eficiencia computacional.

Métodos numéricos Nivel Universidad
Bien si estas leyendo esto sigue toda la ruta de matemáticas para programación.
Fundamental para entender esta ruta de IA y ML.

Es un buen método. No sabía de esto. El código puede mejorarse reemplazando el código de objetivo para que sirva con números decimales y con números entre 0 y 1.

objetivo = float(input('ingresa un numero: '))


RESUMEN:Búsqueda Binaria


Es muy útil para cuando la respuesta se encuentra en un conjunto ordenado.
Es muy eficiente porque corta el espacio de búsqueda en dos por cada iteración.

Requisitos nuestro conjunto debe estar ordenado.
Los números son un conjunto ordenado per se.

Cortamos nuestro espacio de búsqueda a la mitad cada vez.

if __name__ == '__main__':
    entero = int(input('Por favor digita un número para calcular mediante búsqueda binaraia la raíz cuadrada "exacta" de: '))
    #  Epsilon es el valor que indica que tan cerca queremos llegar de nuestra respuesta
    epsilon =0.01
    # Delimitamos el límite inferior
    bajo = 0.0
    # Delimitamos el límite superior
    alto =max(1.0,entero)
    # Delimitamos la mitad del conjunto.
    respuesta = (alto +bajo)/2


    while abs(respuesta **2 - entero) >= epsilon:
        print(f'bajo={bajo}, alto={alto},respuesta={respuesta}')
    # Requiero declarar la mitad y decirle que cuando encuentre la mitad me reasigne 
    bajo,alto,respuesta y siga calcuando mis aproximaciones en términos de potencias
        if respuesta **2 < entero:
             bajo =respuesta
        else:
             alto =respuesta
        respuesta = (alto +bajo)/2
    print(f'La raíz cuadrada exacta de {entero} es {respuesta}')

_________________ Me retorna
bajo=0.0, alto=144,respuesta=72.0 ---> mi respuesta es la mitad de 0 a 144.
bajo=0.0, alto=72.0,respuesta=36.0 ---> mi respuesta es la mitad de 0 a 72.
bajo=0.0, alto=36.0,respuesta=18.0
bajo=0.0, alto=18.0,respuesta=9.0
bajo=9.0, alto=18.0,respuesta=13.5 ---> mi respuesta es la mitad de 9 a 18.
bajo=9.0, alto=13.5,respuesta=11.25
bajo=11.25, alto=13.5,respuesta=12.375
bajo=11.25, alto=12.375,respuesta=11.8125
bajo=11.8125, alto=12.375,respuesta=12.09375
bajo=11.8125, alto=12.09375,respuesta=11.953125
bajo=11.953125, alto=12.09375,respuesta=12.0234375
bajo=11.953125, alto=12.0234375,respuesta=11.98828125
bajo=11.98828125, alto=12.0234375,respuesta=12.005859375
bajo=11.98828125, alto=12.005859375,respuesta=11.9970703125
bajo=11.9970703125, alto=12.005859375,respuesta=12.00146484375
bajo=11.9970703125, alto=12.00146484375,respuesta=11.999267578125
La raíz cuadrada exacta de 144 es 12.0003662109375

A veces la primera aproximación debe ser tratar de encontrar todo, al no tener una forma lógica de llegar a todas las soluciones, busca todas las posibilidades.

nu_metodo = int(input('Seleccione un metodo:  1_Exhaustiva; 2_Aproximación; 3_Binaria: '))
if nu_metodo == 1:
    objetivo = int(input('Ingresa un entero: '))
    
    def exhaustiva (objetivo):    
        respuesta = 0

        while respuesta**2 < objetivo:
            respuesta +=1
            print(respuesta)
            
        if respuesta**2 == objetivo:
            print(f'la raiz cuadrada de {objetivo} es {respuesta}')
        else:
            print(f'{objetivo} no tiene una raiz cuadrada exacta')
    exhaustiva(int(objetivo))  


elif nu_metodo == 2:
     objetivo = int(input('Ingresa un entero: '))
     def aproximacion (objetivo):
        epsilon = 0.01
        #------------------------------epsilon a mayor velocidad menor exactitud y viceversa
        paso = epsilon**2
        respuesta = 0.0

        while abs(respuesta**2 - objetivo) >= epsilon and respuesta <= objetivo:
            
            respuesta += paso
            
            
        if abs(respuesta**2 - objetivo) >= epsilon:
            print('No se encontro la raiz cuadrada del {objetivo}')   
        else:
            print(f'La raiz cuadrada de {objetivo} es {respuesta}')
     aproximacion(int(objetivo))    

else:
    objetivo = int(input('Ingresa un entero: '))    
    def binaria (objetivo):
        epsilon = 0.01
        bajo = 0.0
        alto = max(1.0, objetivo)
        respuesta = (alto + bajo) / 2

        while abs(respuesta**2 - objetivo) >= epsilon:
        
            if respuesta**2 < objetivo:
                bajo = respuesta
            else:
                alto = respuesta
            respuesta = (alto + bajo) / 2
        print(f'La raiz cuadrada de {objetivo} es {respuesta}')
    binaria(int(objetivo))  




epsilon = 1.0
la raíz de 144 es 12.0234375, el numero de interaciones fueron 10

epsilon = 0.1
la raíz de 144 es 11.9970703125, el numero de interaciones fueron 13

epsilon = 0.01
la raíz de 144 es 12.0003662109375, el numero de interaciones fueron 16

epsilon = 0.001
la raíz de 144 es 12.000022888183594, el numero de interaciones fueron 20

epsilon = 0.0001
la raíz de 144 es 11.99999713897705, el numero de interaciones fueron 23

epsilon =0.00001
la raíz de 144 es 12.000000357627869, el numero de interaciones fueron 26

objetivo = int(input("Escribe un número: "))
epsilon = 0.00001
bajo = 0.0
alto = max(1.0,objetivo)
respuesta = (alto + bajo)/2
Num_interaciones =0 
while abs(respuesta**2-objetivo) >= epsilon:
    Num_interaciones +=1
    print(f'Bajo ={bajo}, Alto ={alto},Respuesta = {respuesta}')
    if respuesta**2 < objetivo:
        bajo = respuesta
    else:
        alto = respuesta 

    respuesta =(alto + bajo)/2  

print(f'la raíz de {objetivo} es {respuesta}, el numero de interaciones fueron {Num_interaciones}') ```

Hola, quise hacer esta aportación para los que hemos tenido dificultad con entender el fundamento matemático más que el algoritmo. Aquí les dejo unos puntos importantes que espero les sirva para entender mejor la clase:
-Recordemos la relación que existe entre la potencia y la raíz. En nuestro programa queremos obtener la raíz cuadrada de un número denominado radicando (variable objetivo). Partiendo de esto, podríamos decir que el resultado de una raíz es la base de una potencia (señalados en azul), y que el radicando de una raíz, es el resultado de una potencia (señalados en verde). Es por lo anterior que en nuestro programa, debemos de elevar al cuadrado la variable “respuesta”.
-Ahora que establecimos la relación entre potencia y raíz, lo que buscamos es el valor de la “base” de la potencia para obtener el “resultado de la raíz”. ¿De donde debemos de partir para encontrar este valor? Bueno, en este caso emplearemos la búsqueda binaria para irnos aproximando a este valor.
-Aplicar el método de búsqueda binaria requiere de un parámetro que nos indique qué tan cerca estamos de la respuesta en cada iteración que se ejecuta en el ciclo while. Es aquí donde entra en acción el error absoluto (señalado en rojo), el cual nos dará la diferencia entre el “valor real” y el “valor aproximado” obtenido en cada iteración. El error absoluto es lo que conocemos como epsilon y es lo que nos indicará la mínima diferencia que aceptaremos como error. Si nos centramos en el ejemplo de la imagen, veremos que al buscar la raíz cuadrada de 49, tendremos un error absoluto igual a cero, dado que es una raíz exacta. OJO: si buscamos la raíz de 49 en nuestro programa, no obtendremos un valor exacto porque estamos usando el tipo de dato flotante.

quisiera dar un me encorazona enserio que es muy util este curso ♣

Descripción del recorrido del código

Intente describir como es el recorrido del código para así comprender y aprender más.
Espero les sirva como me sirvió a mi. ☺️

objetivo =int(input('Escoge un número '))
epsilon = 0.01 #margen de error
bajo = 0.0 #nuestro limite inferior
alto = max(1.0, objetivo) #uncion max que nos regresa el valor más alto entre ambos valores.
respuesta = (alto + bajo)/2 

while abs(respuesta**2 - objetivo) >= epsilon:
    print(f'bajo={bajo}, alto={alto}, respuesta={respuesta}')
    if respuesta**2 < objetivo:
        bajo = respuesta
    else:
        alto = respuesta
        
    respuesta = (alto + bajo)/2 
    #En cada iteracion estamos dividiendo entre 2 nuestro espacio de búsqueda.
print(f'La raiz cuadrada de {objetivo} es {respuesta}') 

Para este ejemplo ingrese el número 9 😄
.

Empezamos

Al iniciar nuestro código: indicamos que el objetivo es 9, nuestro margen de error épsilon es de 0.01, el valor de bajo es 0.0 y alto tomara el valor máximo, ya sea 1.0 ó el objetivo, que para este caso es el 9 y el valor de respuesta será (alto + bajo)/2 = 4.5.
.
Al iniciar la iteración, el loop (while) pregunta si abs(respuesta**2 – objetivo) es mayor o igual que nuestro margen de error épsilon, para así continuar con el loop. Entonces 4.5**2 – 9 es 11.25 y es mayor que épsilon 0.01, entonces iniciamos nuestro loop (while), al iniciar el loop imprime los valores obtenidos de bajo, alto y respuesta. Se muestran como resultado en la 1ra línea.
.
bajo = 0.0, alto = 9, respuesta= 4.5
.
En la siguiente condición preguntamos si respuesta**2 es menor que el objetivo 9, entonces bajo = respuesta y si no cumple la condición, alto = respuesta.
Para este caso 4.5**2 = 20.25 es mayor al objetivo, entonces alto = 4.5.
y bajo mantendrá su valor 0.0
Entonces el nuevo valor de respuesta (alto + bajo)/2 será (4.5 + 0.0)/2 = 2.25
.
Otra vez iteramos, empezamos desde la parte inicial del loop.
Al iniciar el loop pregunta si abs(respuesta**2 – objetivo) es mayor o igual que nuestro margen de error épsilon 0.01. Para así continuar con la iteración. Entonces 2.25.**2 – 9 es -3.9375 y el valor absoluto (abs) es 3.9375 y es mayor al épsilon 0.01 por tanto continuamos con el loop
.
El loop imprime los nuevos valores obtenidos de bajo, alto y respuesta.
Se muestran como resultado en la 2da linea.
.
bajo = 0.0, alto = 4.5, respuesta= 2.25
.
Continuando en la siguiente condición pregunta si respuesta**2 es menor que el objetivo, entonces bajo = respuesta y si no cumple la condición, alto = respuesta.
Para este caso 2.25**2 = 5.0625 es menor al objetivo 9, entonces bajo = 2.25 y alto mantiene su valor de 4.5.
El nuevo valor de respuesta (alto + bajo)/2 será (2.25 + 4.5)/2 = 3.375
De esta manera obtenemos los valores de la 3ra línea que será impreso en la siguiente iteración.
.
bajo = 2.15, alto = 4.5, respuesta= 3.375
.
De esta manera continuaremos hasta que no se cumpla la condición de inicio del loop (while) que está definido por nuestro margen de error épsilon.
En los últimos valores obtenidos tendremos como resultado final el valor de bajo=2.9970703125, alto = 3.005859375 y el nuevo valor de respuesta (alto + bajo)/2 será (3.005859375 + 2.9970703125)/2 = 3.001464844375.
Solo que estos valores ya no serán impresos en la consola ya que al preguntar otra vez en la iteración si la condición abs(respuesta**2 – objetivo) es mayor o igual que el épsilon, da como resultado 0.008791212 que es menor al epsilon 0.01. por lo tanto, finaliza el loop.
.
💚 😄 Espero ayude!

Me voló la cabeza esto jajajaja

Si desean profundizar más en el tema a la par que toman el curso les recomiendo esta playlist que realizó el canal Dimath en la cual habla de métodos numéricos muy bien explicados.
https://www.youtube.com/playlist?list=PL1fzt-aRc08oHfVjlowXWvaZ8wdk35Lir

Con el anterior algoritmo me aburrí de esperar jajajaja, así que le quite un 0 y le puse un contador de iteraciones que me dijera al final cuantas había usado y fueron cerca de 2M, con este es extremadamente rápido.

Les recomiendo el método de Horner en el cálculo de raíz de un polinomio aislada en un intervalo, ya que tiene ideas muy parecidas a esta. Método de Horner

Buena explicación.

def metodo1():
    objetivo = int(input('Escoge un numero: '))
    epsilon = 0.001
    bajo = 0.0
    alto = max (1.0 , objetivo)
    respuesta = (alto + bajo) / 2

    while abs(respuesta**2 - objetivo) >= epsilon:
        print(f'bajo={bajo}, alto={alto}, respuesta={respuesta}')
        if respuesta**2 < objetivo:
            bajo = respuesta
        else:
            alto = respuesta
        respuesta = ( alto + bajo ) /2
        print ( f'la raiz cuadrada de {objetivo} es la {respuesta}')

def metodo2():
    objetivo = int(input('Escoge un numero: '))
    epsilon = 0.1
    paso = epsilon**2 
    respuesta = 0.0

    while abs(respuesta**2 - objetivo) >= epsilon and respuesta <= objetivo:
        print(abs(respuesta**2 - objetivo), respuesta)
        respuesta += paso

    if abs(respuesta**2 - objetivo) >= epsilon:
        print(f'No se encontro la raiz cuadrada {objetivo}')
    else:
        print(f'La raiz cudrada de {objetivo} es {respuesta}')

menu = """
Bienvenido al programa
1 -metodo biseccion
2 -metodo cartesiano
Elige una opcion "1" "2"
"""


opcion = int(input(menu))
if opcion == 1: 
    metodo1()

elif opcion == 2:
    metodo2()

else:
    print(f' ingresa una opcion correcta')``````

oye no guardaste el código jajaj por eso te cargo muy rápido 😉

Los errores también son nuestros aliados, ya que nos dice en que nos equivocamos y lo que debemos ajustar.

Que pasa si epsilon es igual a cero ?

Aquí les dejo un resumen de mi código!

import time 

def run():
    objetivo = int(input("Escoge un número: "))
    epsilon = 0.01
    bajo = 0.0
    alto = max(1.0, objetivo)
    respuesta = (alto + bajo) / 2
    num = 0

    start = time.time()

    while abs(respuesta**2 - objetivo) >= epsilon:
        print(f'bajo = {bajo}, alto = {alto}, respuesta = {respuesta}')
        if respuesta**2 < objetivo:
            bajo = respuesta
        else:
            alto = respuesta

        respuesta = (alto + bajo) / 2
        num += 1

    end = time.time()

    print(f'Para resolver el problema se hicienron {num} iteraciones en {end-start} segundos')
    print(f'La raíz cuadrada de {objetivo} es {respuesta}')


if __name__ == "__main__":
    run()

Codigo de la clase y comentarios :

objetivo = int(input('Escoge un numero: '))
epsilon = 0.01
bajo = 0.0
alto = max(1.0, objetivo)
# la funcion max regresa el valor mas alto entre 2 valores
"""entonces ahi dice que regreese 1.0 o el objetivo si el objetivo es menor a 1.0 vamos a empezar directo
de 1.0 """
respuesta = (alto + bajo)/2
# siempre se divide entre 2

while abs(respuesta**2 - objetivo) >= epsilon:
    print(f'bajo={bajo} alto={alto}, respuesta={respuesta}')
    if respuesta**2 < objetivo:
        bajo = respuesta
    else:
        alto = respuesta
    respuesta = (alto + bajo) / 2

""" ¿Porque la respuesta de alto y bajo se divide entre 2? para hacerla mas pequeña en cada iteracion 

Recuerda que en el espacio de busqueda se esta dividiendo entre 2"""
print(f'La raiz cuadrada de {objetivo} es {respuesta}')```


Recordar que la busqueda binaria unicamente funciona cuando nuestro conjunto tiene un orden, si no hay que explorar todas las opciones

Tremendo, me tomó mas de un millón de iteraciones usando el mismo epsilon con el método de aproximación…

Con el método anterior la raiz cuadrada de 4 y con un error del 0.01:

La raiz cuadrada de 4 es 1.9974999999997964
El programa demoró 1.9241416454315186 segundos

Con la busqueda binaria la raiz cuadrada de 4 y con un error del 0.0001:

La raiz cuadrada de 4 es 2.0
El programa demoró 0.0010004043579101562 segundos

Número = 4

Para epsilon = 0.001:
Raiz cuadrada fue: 1.999749999925672
Número de iteraciones fue de: 1.999.750

Para epsilon = 0.0001
Raiz cuadrada fue: 1.999975006212548
Número de iteraciones fue de: 199.997.501

Este algoritmo es sumamente rápido. De hecho es también utilizado en la electrónica para convertidores Análogos/Digitales (ADCs). Donde internamente hay un Digital/Analógico (DAC) tratando de igualar la respuesta de la entrada. Cuando por fin encuentra una buena aproximación (en este caso la épsilon es la resolución en bits del convertidor 1/1024 si es de 10 bits) guarda el dato en una dirección de memoria para utilizarlo por el programa,

muy piola

Me recuerda mucho a mi clase de métodos numéricos que tomé en la universidad

Me ha costado un poco este ejercicio pero lo he comprendido, muy interesante

Excelente. Mucho más simplificada la búsqueda binaria de esta manera.

Si están usando python3.8 o mayor, el print lo pueden hacer de la siguiente manera:
print(f’{bajo=}, {alto=}, {respuesta=}’)

objetivo = int(input('Escoge un numero: '))
epsilon = 0.01
bajo = 0.0
alto = max(1.0, objetivo)
respuesta = ( (alto + bajo) / 2 )

while abs(respuesta**2 - objetivo) >= epsilon:
  print(f'bajo={bajo}, alto={alto}, respuesta={respuesta}')
  if respuesta**2 < objetivo:
    bajo = respuesta
  else:
    alto = respuesta

  respuesta = (alto + bajo) / 2

print(f'La raiz cuadrada de {objetivo} es {respuesta}')
print('')
print(f'bajo={bajo}, alto={alto}, respuesta={respuesta}')```

Para l@s que se lo pregunten, la complejidad del algoritmo de búsqueda binaria es O(log(n)). Una de las mejores complejidades a llegar en lo que respecta a un arreglo ordenado de información.

Definitivamente es algoritmo es mucho mas eficciente que el anterior.

Es un algoritmo muy bien pensado y aprovechando al máximo la posibilidad de aproximación.

genial, es increíble como los algoritmos pueden ir evolucionando, y de esa forma funcionen de forma mas eficiente

puse como variable 2 y un error de 1*10**-16(todavía está corriendo hace 10 minutos ).tengo una notebook

Muy interesante, tarda un enter

Les compartó un post con un resumen sobre Búsqueda Binaria.

me gusta ver los print de los statement, y como va buscando la respuesta mas precisa

cuando dice “vamos a nuestro IDE” … se que se va poner hardcore

Creo que una buena práctica será desempolvar todas esas clases de matemáticas donde se hacían los cálculos sin calculadora y a partir de ellos hacer algoritmos básicos.

No se si sera mi portátil pero en el ejercicio pasado pasaron mas de 30 minutos y no se detenía así que me toco cerrar ahora ni un segundo. Aun no me queda claro la parte matemática del algoritmo y me gustaría que cambiaran los tecnicismos o los aclararan un poco mas. Gracias.

Este es mi codigo. Cuenta el numero de iteraciones

numero  = int(input('Escoge un numero: '))
epsilon = float(input('Precision: '))

iteracion = 1
bajo = 0
alto = numero / 2
respuesta = (alto + bajo)/2
gap = (respuesta**2 - numero)

while abs(gap) >= epsilon:
    print(f'{iteracion} {gap} {respuesta}') 
    if gap < 0:
        bajo = respuesta
    else:
        alto =respuesta
    respuesta = (alto + bajo)/2
    gap = (respuesta**2 - numero)
    iteracion += 1 
print(f'{iteracion} {gap} {respuesta}')

print(f'La raiz cuadrada de {numero} es = {respuesta} obtenida en {iteracion} iteraciones')

La busqueda binaria funciona siempre y cuando nuestro conjunto tenga un orden!

goal = int(input('Choose a number: '))
epsilon = 0.001
low = 0.0
high = max(1.0, goal)
answer = (low + high) / 2


while abs(answer**2 - goal) >= epsilon:
    print(f'low= {low}, high= {high}, answer= {answer}')
    if answer**2 < goal:
        low = answer
    else:
        high = answer
    
    answer = (low + high) / 2

print(f'The square root of {goal} is {answer}')

Usando búsqueda binaria queda así:
precisión = 0.01//3.665 s
precisión = 0.001//2.599 s
precisión = 0.0001//2.428 s
precisión = 0.00001//2.795 s
precisión = 0.000001//2.247 s

Alguien que me pueda explicar a qué hace referencia la variable **epsilon **y cual es su función?

me costó un poco entenderlo pero hice finalmente mi propio ejemplo, les dejo el codigo de un algoritmo para que sea el computador quien debe encontrar el numero que estoy pensando (del 1 al 1000), al hacerlo con busqueda binaria no demora mucho en encontrarlo.

import random

def run():
    numero = random.randint(1,1000)
    inicio=0
    fin=1000

    respuesta = input(f'el numero que esta pensando es mayor, menor o igua a {numero}? ')

    while respuesta != "igual":
        if respuesta == "mayor":
            inicio = numero + 1
            numero = (inicio + fin)//2
        elif respuesta == "menor":
            fin = numero - 1
            numero = (inicio + fin) //2

        respuesta = input(f'el numero que esta pensando es mayor, menor o igua a {numero}? ')
    
    print (f'tu numero es: {numero}')


if __name__=='__main__':
    run()

En el código hay un problema si queremos bajar el epsilon a números muy pequeños y es que llega un momento en el que respuesta no puede tener más decimales, por eso hay que poner una bandera que diga que si mi respuesta ya no cambia, se salga del programa, ésto lo logramos con:

if (alto+bajo)/2!=respuesta:
  respuesta=(alto + bajo) / 2
else:
  break

Mi código completo sería

objective = None
epsilon = 0.000000001
low = 0.0
i = 0


steps=epsilon**2
result=0.0
taken=0

while objective == None:
  objective_string = input('Which number do you wanna get the square root?  ')
  if(objective_string.isdigit()):
    objective = int(objective_string)

high = max(1.0, objective)

while abs(result**2-objective) >= epsilon:
  if result**2 < objective:
    low = result
  else:
    high = result
  if (high+low)/2!=result:
    result=(high + low) / 2
  else:
    break
  i+=1
  print(f'{i}: high={high}, low={low}, result={result}')


print(f'square of {objective} is equal to {result}')

Puedes poner cualquier número que alcance la definición de float, como:

  • 12345678901234567890123456789012345678901234567890123456789012345678901234567890123123123
    .
    Para el caso anterior se tarda 199 pasos en encontrar la respuesta 🤩:
square of 12345678901234567890123456789012345678901234567890123456789012345678901234567890123123123 is equal to 1.111111106111111e+44
Chicos todo perfecto pero me perdí leyendo el código con calma cuando el valor de respuesta pasar a ser el límite bajo, lo hice en este caso con 144 con un epsilon de 0.1, me ayudan por fa? ![](https://static.platzi.com/media/user_upload/image-6fc1e28f-ac91-43fa-9862-171d5c091a3d.jpg)
def enumeracion(objetivo):    respuesta = 0     while respuesta\*\*2 < objetivo:        respuesta += 1        if respuesta\*\*2 == objetivo:        print(f"La raiz cuadrada de {objetivo} es {respuesta}")     else:        print(f"{objetivo} no tiene una raiz cuadrada exacta") def aproximacion(objetivo):    epsilon = 0.0001    paso = epsilon\*\*2    respuesta = 0.0     while abs(respuesta\*\*2 - objetivo) >= epsilon and respuesta <= objetivo:        respuesta += paso     if abs(respuesta\*\*2 - objetivo >= epsilon):        print (f"No se encontró la raíz cuadrada del {objetivo}")     else:        print(f"La raiz cuadrada de {objetivo} es {respuesta}") def busqueda\_binaria(objetivo):    epsilon = 0.001    bajo = 0.0    alto = max(1.0, objetivo)    respuesta = (alto + bajo) / 2     while abs(respuesta\*\*2 - objetivo) >= epsilon:                if respuesta\*\*2 < objetivo:            bajo = respuesta        else:            alto = respuesta         respuesta = (alto + bajo) / 2     print(f"La raiz cuadrada de {objetivo} es {respuesta}") objetivo = int(input("Selecciona un número: ")) print("Opción 1 enumeracion, Opción 2 aproximacion, Opción 3 busqueda\_binaria")opcion = int(input("Selecciona una opción para obtener el resultado: ")) if (opcion == 1):    enumeracion(objetivo) if (opcion == 2):    aproximacion(objetivo) if (opcion == 3):    busqueda\_binaria(objetivo)
Estoy entendiendo parte por parte, y me causa duda, de dónde se sabe que si la respuesta al cuadrado que tenemos es mayor o menor al objetivo se tiene que actualizar "bajo" o "alto" como nueva respuesta
Este algoritmo es muy rápido a pesar de colocarle la siguiente parametrizaciòn: ![](https://static.platzi.com/media/user_upload/Screenshot%20from%202024-02-15%2016-11-10-6046ce87-eed8-425a-b22e-0fa930a4b6d1.jpg) ![](https://static.platzi.com/media/user_upload/Screenshot%20from%202024-02-15%2016-10-50-8eddbe1d-e9d1-4e21-a618-40ce83971421.jpg)
```js objetivo = int(input("Escoge un numero: ")) epsilon = 0.001 bajo = 0.0 alto = max(1.0, objetivo) respuesta = (alto+ bajo)/2 while abs(respuesta**2 - objetivo) >= epsilon: print(f"bajo = {bajo}, alto = {alto}, respuesta= {respuesta}") if respuesta**2 <objetivo: bajo = respuesta else: alto = respuesta respuesta = (alto + bajo)/2 print(f"La raiz cuadrada de {objetivo} es {respuesta}") ```objetivo = int(input("Escoge un numero: "))epsilon = 0.001bajo = 0.0alto = max(1.0, objetivo)respuesta = (alto+ bajo)/2 while abs(respuesta\*\*2 - objetivo) >= epsilon:    print(f"bajo = {bajo}, alto = {alto}, respuesta= {respuesta}")    if respuesta\*\*2 \

¿Qué significaba abs() en python?

Los metodos numericos son excelentes pero mira como hoy lo hace ADA es algo super rapido import math numero = float(input("Ingresa un número: ")) raiz\_cuadrada = math.sqrt(numero) print("La raíz cuadrada de", numero, "es:", raiz\_cuadrada)

Mmm… que muegrero

Este codigo que se encuentra aqui abajo fue escrito completamente por el Chatgpt lo unico que yo agregue fue el Input,creo que llego a la misma conclusion,obviamaente que el codigo del profesor es mucho mas limpio por ende mejor escrito pero es impresionante lo rapido que lo hizo

def calcular_raiz_cuadrada(numero):
if numero < 0:
return “Error: No se puede calcular la raíz cuadrada de un número negativo.”

if numero == 0:
    return 0.0

min_valor = 0.0
max_valor = max(1.0, numero)  # El valor máximo es el número mismo si es menor que 1, de lo contrario es 1.0

while max_valor - min_valor > 0.01:
    print(f"min_valor={min_valor}, max_valor={max_valor} ")
    medio = (max_valor + min_valor) / 2
    cuadrado_medio = medio * medio
    
    if cuadrado_medio == numero:
        return medio
    
    if cuadrado_medio < numero:
        min_valor = medio
    else:
        max_valor = medio

return (max_valor + min_valor) / 2

numero = int(input("Escoge un numero “))
raiz_cuadrada = calcular_raiz_cuadrada(numero)
print(f"La raíz cuadrada de {numero} es aproximadamente {raiz_cuadrada}”)

Me gustó esta explicación de la " f " que me da Chat GPT:

En Python, el prefijo “f” antes de un string indica que es una cadena de formato (format string). Es una característica introducida en Python 3.6 que permite realizar interpolación de variables dentro de una cadena de manera más concisa y legible.

Cuando se utiliza el prefijo “f” en una cadena, puedes incluir expresiones dentro de llaves “{}” dentro de la cadena. Estas expresiones serán evaluadas y el resultado se insertará en la cadena. Aquí tienes un ejemplo:

python
Copy code
nombre = "Juan"
edad = 30
cadena = f"Hola, me llamo {nombre} y tengo {edad} años."
print(cadena)

14. Búsqueda Binaria

  • Cuando la respuesta se encuentra en un conjunto ordenado, podemos utilizar búsqueda binaria.
  • Es altamente eficiente, pues corta el espacio de búsqueda en dos por cada iteración
  • En el algoritmo anterior con el número más alto tardó 18 segundos, con este algoritmo el número más alto tardó 3 segundos.
objetivo = int(input('Escoge un número: '))
epsilon = 0.001
bajo = 0.0
alto = max(1.0, objetivo)
respuesta = (alto + bajo) / 2

while abs(respuesta**2 - objetivo) >= epsilon:
    print(f'bajo={bajo}, alto={alto}, respuesta={respuesta}')
    if respuesta**2 < objetivo:
        bajo = respuesta
    else:
        alto = respuesta
    
    respuesta = (alto + bajo) / 2

print(f'La raíz cuadrada de {objetivo} es {respuesta}')

Dejo una solución propia para encontrar la raiz cuadrada exacta de un numero usando busqueda binaria. Si la encuentra la devuelve y caso contrario informa que no existe entre los enteros. Como novedad usé listas, list comprehensions y slicing para su resolución. Aquí el codigo:

# Para realizar busqueda binaria el pre requisito sine qua non es que nuestro universo de busqueda esté ordenado. 
# Mi propia solución: 

objetivo = int(input("Escoge un entero: "))

respuestas_posibles = [x for x in range(1, objetivo//2 + 1)]

respuesta = 0

print(f'Las respuestas posibles son: {respuestas_posibles}')

while (respuesta ** 2) != objetivo and len(respuestas_posibles) > 1:
    
    respuesta = respuestas_posibles[len(respuestas_posibles)//2]
    print(f'La respuesta aproximada sería: {respuesta}')

    if (respuesta ** 2) > objetivo:
        respuestas_posibles = respuestas_posibles[:len(respuestas_posibles)//2]
        print(f'Las proximas respuestas posibles son: {respuestas_posibles}')
    else:
        respuestas_posibles = respuestas_posibles[len(respuestas_posibles)//2:]
        print(f'Las proximas respuestas posibles son: {respuestas_posibles}') 

if (respuesta ** 2) == objetivo: 
    print(f'La raiz cuadrada de {objetivo} es {respuesta}')
else:
    print(f'El numero {objetivo} no tiene raiz cuadrada entre los enteros')

Espero les guste.

Divide and conquer

Mi còdigo con sus explicaciones.

# Pedimos al usuario que ingrese un número objetivo
objetivo = int(input('Escoge un número: '))

# Establecemos la precisión deseada para el cálculo de la raíz cuadrada
epsilon = 0.01

# Establecemos los valores iniciales para la búsqueda binaria
bajo = 0.0
alto = max(1.0, objetivo)

# Establecemos la primera aproximación de la raíz cuadrada
respuesta = (alto + bajo) / 2

# Iniciamos el bucle while para buscar la raíz cuadrada
while abs(respuesta**2 - objetivo) >= epsilon:
    # Imprimimos los valores actuales de bajo, alto y respuesta
    print(f'bajo={bajo}, alto={alto}, respuesta={respuesta}')
    
    # Comprobamos si la respuesta al cuadrado es menor que el objetivo
    if respuesta**2 < objetivo:
        # Si es así, la raíz cuadrada se encuentra en el intervalo entre respuesta y alto
        # Así que actualizamos el valor de bajo
        bajo = respuesta
    else:
        # Si no, la raíz cuadrada se encuentra en el intervalo entre bajo y respuesta
        # Así que actualizamos el valor de alto
        alto = respuesta
    
    # Calculamos la nueva aproximación de la raíz cuadrada utilizando la fórmula de búsqueda binaria
    respuesta = (alto + bajo) / 2

# Cuando el bucle ha terminado, imprimimos el resultado final
print(f'La raíz cuadrada de {objetivo} es {respuesta}')

Definitivamente he encontrado mi lugar en el mundo de la programación

Búsqueda binaria 0️⃣1️⃣


La búsqueda binaria es un algoritmo de búsqueda muy eficiente que permite encontrar rápidamente un elemento en una lista ordenada. En lugar de buscar el elemento en toda la lista, la búsqueda binaria divide la lista por la mitad en cada iteración, y luego se enfoca en la mitad donde el elemento podría estar presente.
.
Por ejemplo, supongamos que tienes una lista de números ordenados del 1 al 100 y quieres encontrar el número 54. En lugar de buscar el número de manera lineal, la búsqueda binaria tomará el número en el medio de la lista, que es 50. Como 54 es mayor que 50, la búsqueda binaria descartará la mitad inferior de la lista y continuará buscando en la mitad superior. Luego, toma el número en el medio de esa mitad (entre 51 y 100), que es 75, y descarta la mitad inferior de nuevo. Continúa dividiendo la lista por la mitad en cada iteración hasta que encuentre el número deseado.
.
Un dato interesante es que el algoritmo de búsqueda binaria tiene una complejidad de tiempo de O(log n), lo que significa que su tiempo de ejecución aumenta de manera logarítmica con el tamaño de la lista. Esto lo hace mucho más rápido que la búsqueda lineal, que tiene una complejidad de tiempo de O(n), donde n es el tamaño de la lista. Además, la búsqueda binaria es muy utilizada en aplicaciones donde se necesita una búsqueda rápida en grandes conjuntos de datos ordenados, como en bases de datos o en la búsqueda en internet.

La función max() es una función incorporada de Python que devuelve el valor más grande de uno o más argumentos. Puede tomar cualquier número de argumentos, ya sean números, cadenas de texto, listas, tuplas, conjuntos, etc.

Comparto mi código explicado, ojalá a alguien le resulte útil.


#Este es el número al cual queremos hallar la raíz cuadrada.
objetivo = int(input('Escoge un número: '))

#Este es el margen de error que admitimos en la respuesta de la raíz cuadrada.
epsilon = 0.01

#Valor mínimo en el conjunto de posibles números que contienen a la respuesta.
#Se va actualizando tras cada iteración, acercándose a la raíz cuadrada que queremos hallar.
bajo = 0.0

#Valor máximo en el conjunto de posibles números que contienen a la respuesta.
# Se va actualizando tras cada iteración, acercándose a la raíz cuadrada que queremos hallar.
alto = max(1.0, objetivo)

#respuesta Es la raíz cuadrada que queremos encontrar. 
#Si la respuesta calculada tiene un margen de error superior a 0.01, entonces se actualizará este valor en la siguiente iteración.
#Este valor se actualiza calculando el promedio entre alto y bajo.
respuesta = (alto+bajo)/2

#Continuar con el while, siempre y cuando la respuesta tenga un margen de error superior a epsilon (0.01).
while abs(respuesta**2 - objetivo) >= epsilon:
    
    #Si la respuesta al cuadrado es menor que el objetivo, este valor de la respuesta será nuestro nuevo bajo.
        #Es decir, no nos sirven números menores que el actual, así que en adelante no se buscarán números menores a este.
    if respuesta **2 < objetivo:
        bajo = respuesta
        
    #De lo contrario, si la respuesta al cuadrado es mayor que el objetivo, ahora este valor será nuestro nuevo alto.
    #Es decir, no nos sirven números más altos que el actual, así que en adelante no se buscarán números mayores a este.
    else:
        alto = respuesta
    
    #Definimos el nuevo valor que probaremos para la respuesta, hallando el promedio entre el valor alto y bajo.
    respuesta = (alto + bajo)/2
    
    
#Cuando el while se interrumpa (es decir, cuando el margen de error sea igual o menor a epsilon (0.01), imprimir la respuesta.
print(f'La raíz cuadrada de {objetivo} es {respuesta}') 

//Este método reduce el número de iteraciones para llegar a la respuesta real a través de proponer combinaciones en función a dos posibles valores (uno alto y otro bajo) que se irán promediando para mostrar posibles respuestas; dependiendo si la respuesta propuesta al cuadrado, en cada ciclo es mayor o menor al objetivo irán mutando ambas partes recibiendo el valor promedio para acercarse (ya sea para abajo o para arrbia) a la combinación correcta que de como resultado la raiz real del valor objetivo.

Este algoritmo es mucho mas efectivo!! Casi romp mi pc con el anterior. Que pena que solo funciona cuando esta ordenado el conjunto 🥴