Implementación Recursiva de Búsqueda Binaria
Contenido del curso
Josue Noha Valdivia
Alonso Cangalaya
Emiliano Ibarra
Walter Correa
Anderson Steven Mendez Chipatecua
Maria Guadalupe Diaz Escobar
JESUS ALBERTO CARREÑO MARTINEZ
JESUS ALBERTO CARREÑO MARTINEZ
JESUS ALBERTO CARREÑO MARTINEZ
John Fredy Higuita Porras
Omar Rodríguez Aldama
victor rodriguez
Jordan Bonnett Gomez
victor rodriguez
Karl Behrens Gil
Gabriel Missael Barco
Mauricio Gonzalez Falcon
Alveiro Mejia Lopez
Luis Fernando Pedroza Taborda
Mario Estanislao César Ariet
Tomas Filippo
Joel Orellana
Christian Mahonry Colorado Bulbarela
Eduardo Jimenez
Jaime Eduardo González Meléndez
Cristian Fabián Aroca Espinosa
giani reyes nieto
Jose Fernando Jaramillo Boon
Omar Daniel Centeno
Pablo Antipan Quiñenao
Gonzalo Ferrando
Jhonathan Alberto López Gamarra
Sebastian Cifuentes
Anthony Guzman Lopez
Maximo Daniel Di napoli
Yilmer Ramiro Guativa Rincón
Nicolás Arias González
Moisés Manuel Morín Hevia
Pablo Felipe Chaparro Hurtado
Kevin Morales
Luis Mojica
Profesor
Néstor Duque
Kevin Inca
Alberto Castro Flores
Willington Ortiz
Alberto Castro Flores
Wow se nota la efieciencia del codigo:
import random def busqueda_lineal(lista, objetivo,iter_lin=0): match = False for elemento in lista: iter_lin+=1 if elemento == objetivo: match = True break return (match,iter_lin) def busqueda_binaria(lista, comienzo, final, objetivo,iter_bin=0): iter_bin+=1 if comienzo > final: return (False,iter_bin) medio = (comienzo + final) // 2 if lista[medio] == objetivo: return (True,iter_bin) elif lista[medio] < objetivo: return busqueda_binaria(lista, medio + 1, final, objetivo,iter_bin=iter_bin) else: return busqueda_binaria(lista, comienzo, medio - 1, objetivo,iter_bin=iter_bin) if __name__ == '__main__': tamano_de_lista = int(input('De que tamaño es la lista? ')) objetivo = int(input('¿Qué número quieres encontrar? ')) lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)]) (encontrado,iter_bin) = busqueda_binaria(lista, 0, len(lista), objetivo) (encontrado,iter_lin) = busqueda_lineal(lista, objetivo) #print(lista) print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista') print(f'Iteraciones busqueda lineal: {iter_lin}') print(f'Iteraciones busqueda binaria: {iter_bin}')
Excelente!!! , me hiciste ver que las las funciones pueden retornar 2 valores, ya que en tu código retornas el estado True or False y el valor int de las iteraciones (iter_bin y iter_lin).
Hola! En el print print(f'Iteraciones busqueda lineal: {iter_lin}') no deberia de devolver 45?
Complejidad Algorítmica utilizando el print statement.
A esta forma de cacular la complejidad algoritmica se le podria decir que lo calculaste de forma espacial, como se menciono en las clases anteriores cierto?
Gracias
El profesor en el minuto 12:04 dijo que cuando se trata de acceder mediante indices y venimos de un len le tenemos que restar 1.
Esto es porque len trabaja comenzando desde el 1-final, ya que cuenta los elementos, y nosotros como personas comenzamos a contar desde el 1 y no del cero
En cambio, los indices, trabajan desde el 0, por eso se le resta -1.
En los comentario les dejo un ejercicio para que se puede ilustrar mejor
Ejecuten este código en la consola, linea por linea
`import random lista=[random.randint(0,100) for i in range (10)] print (lista)
len(lista) lista[10] lista[9]`
Basicamente lo que hace este programa es crear una lista de numeros aleatorios del 0 al 100
con len(lista) nos damos cuenta que marca 10 elementos
Y si ponemos lista[10], para, segun nosotros, acceder al ultimo elemento ya que la lista es de 10 elementos, nos encontraremos con un error que dice que el indice proporcionado esta fuera del rango. Esto es porque los indices toman el primer elemento como la posicion 0, entonces si queremos acceder al indice 10 en una lista de 10 numeros, lo que estamos buscando en realidad es el 11vo elemento, por esta razon es que marco el error.
0,1,2,3,4,5,6,7,8,9,10----->Indices 1,2,3,4,5,6,7,8,9,10------->numero de elementos
Asi que para acceder al ultimo elemento en una lista de 10 elementos, tenemos que acceder al indice 9 lista[9]
Por esta razon, es que se resta -1 a los indices
buenisimo
Como dato curioso ... La búsqueda binaria tiene una complejidad de O( log n )
De hecho es de O(log2(n))
Cuando se habla de complejidad la base es 2, por eso no es necesario escribirlo. Ya va implícito.
https://github.com/karlbehrensg/poo-y-algoritmos-python
Búsqueda binaria
La búsqueda binaria toma una estrategia llamada "Divide y conquista", la cual consiste en dividir el problema en 2 en cada iteración. Este algoritmo asume que la lista se encuentra ordenada, por lo que es necesario realizar este paso primero.
La búsqueda binaria es uno de los mejores algoritmos que se tienen hoy en día para búsqueda, ya que reduce significativamente el numero de pasos, y así disminuyendo nuestro Big O.
Para ver de forma practica haremos una búsqueda binaria a través de código. Lo primero que tenemos que realizar es ordenar nuestra lista antes de ejecutar la búsqueda.
import random def busqueda_binaria(lista, comienzo, final, objetivo): print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}') if comienzo > final: return False medio = (comienzo + final) // 2 if lista[medio] == objetivo: return True elif lista[medio] < objetivo: return busqueda_binaria(lista, medio + 1, final, objetivo) else: return busqueda_binaria(lista, comienzo, medio - 1, objetivo) if __name__ == '__main__': tamano_de_lista = int(input('De que tamano es la lista? ')) objetivo = int(input('Que numero quieres encontrar? ')) lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)]) encontrado = busqueda_binaria(lista, 0, len(lista), objetivo) print(lista) print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
Hola :smile:, hice esta gráfica para comparar el número de iteraciones necesarias: !Comparación de algoritmos
Si quieren ver el código para la gráfica, esta en este gist en GitHub.
Gracias!
aquí una buena explicación de por qué el algoritmo es logaritmico https://riptutorial.com/es/algorithm/example/26648/o--log-n--tipos-de-algoritmos
Alveiro muchas gracias por este aporte, me ha servido bastante.
Siendo muy detallista Yo intercambiaría el orden del if elif else para que haga la menor cantidad de comprobaciones porque el
if lista[medio] == objetivo:
es más probable que salte como falso cada vez hasta que lo encuentra. Me parece que esta forma estaría "mejor optimizado"
def busqueda_biseccion(lista,objetivo): mitad = len(lista) //2 indice = mitad while indice >= 0 and indice <= len(lista) and mitad != 0: mitad //= 2 print(mitad) if lista[indice] > objetivo: indice -= mitad elif lista[indice] < objetivo: indice += mitad elif lista[indice] == objetivo: return True else: return False
Buen codigo!!
wow!
Creo que lo correcto es decir que Objetivo > final, en lugar de comienzo > final, ya que esto lo aseguramos con la función sorted y no tiene sentido hacer ese if.
Lo curioso es que al quitar este if, parece que la logica del programa se daña. En mi caso me muestra un RecursionError. "maximum recursion depth exceeded while calling a Python object"
Hice la solución para la búsqueda binaria y sí cuenta el número de iteraciones correctamente, pero marca un error (diría que es un warning, porque el programa sí corre). La implementación la adapté de esta fuente: stackoverflow Si alguien sabe por qué ocurre ese error o warning, lo agradecería.
Creo que esto es debido a que el interprete de Python va leyendo línea por línea y cuando llega a la línea 6, estás diciendo que haga una operación a una variable que no está inicializada aún, la inicialización está más abajo.
Solucionas esto inicializando la variable luego del bloque de import antes de que comiencen las funciones y no abajo donde actualmente está
Genio, quería hacer algo así pero no salió. No entiendo por qué llamas a la función para imprimir las iteraciones
¿Cuál es el peor caso de búsqueda binaria?
¡Hola!
¿Cuál crees tú que sea el peor caso?
El peor caso sería el número que quede en uno de los extremos de la lista en la que estás haciendo la búsqueda.
El peor caso es que el elemento que buscas este en la base del arbol. En ese caso, se realizan log(n), donde n es el numero de total de elemento. Es decir, es un algoritmo de O(log n)
Saludos!
Las pastillas de matrix de Morfeo Tiempo vs Memoria
print statement es mi amigo, lo entendí a la perfección
No he entendido la diferencia entre lista ordenada y lista desordenada, alguien con poderes que me ayude a entender?
Hola sebastian-cifuentes, La lista desordenada quiere decir como esta en el set de datos, como te llega a ti, o como la tomas de una base de datos o un archivo plano; tal cual como fue ingresada, has de cuenta cuando te registras en una pagina para tomar un evento la lista es de los usuarios que se conectan y los toma como van llegando. Por otro lado una lista ordenada siguiendo el ejemplo de los registros para un evento es tomar a todos esos usuarios y ordenarlo por su numero de cedula de menor a mayor de forma numerica.
Espero que la explicación te sea util.
ordenada: 1, 2, 3, 4, 5, 6 desordenada: 4, 5, 1, 3, 2, 6
Cúal es la complejidad algoritmica de la búsqueda binaria?
Es log(n). Puedes ver más detalles sobre la complejidad acá https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search
es logaritmica, de las mejores en cuanto a eficiencia.
Entre búsqueda lineal y búsqueda binaria, cual es mas optimo? cual es mas rápido?
La búsqueda binaria suele ser más efectiva en busquedas grandes, depende de lo que quieres hacer para elegir el tipo de algoritmo.
Básicamente va a depender de si los datos se encuentran ordenados.
Si los datos están desordenados, la búsqueda binaria es equivalente a la búsqueda lineal. Si los datos están ordenados, la búsqueda binaria es mucho más eficiente y rápida.
Siempre y cuando la lista se pueda ordenar la búsqueda binaria siempre será la mejor opción, ya que completa la búsqueda en menor cantidad de iteraciones lo que la hace más eficiente.
import random def busqueda_lineal(lista,objetivo): match = False iteracion_lineal = 0 for elemento in lista: iteracion_lineal +=1 if elemento == objetivo: match = True break return (match,iteracion_lineal) def busqueda_binaria (lista, comienzo, final, objetivo,iteracion_binaria): #print(f'Buscando {objetivo} entre {comienzo} y {final}') if comienzo > final: return False medio = (comienzo+final)//2 iteracion_binaria += 1 if lista[medio]== objetivo: return (True,iteracion_binaria) elif lista[medio] < objetivo: return busqueda_binaria(lista, medio+1, final, objetivo,iteracion_binaria=iteracion_binaria) else: return busqueda_binaria(lista, comienzo, medio-1, objetivo,iteracion_binaria=iteracion_binaria) if __name__ == '__main__': tamano_de_lista = int(input('De que tamano sera la lista?')) objetivo = int(input('Que numero quieras encontrar?')) lista = sorted([random.randint(0,100) for i in range(tamano_de_lista)]) encontrado_lineal = busqueda_lineal(lista, objetivo) encontrado_binario = busqueda_binaria(lista, 0, len(lista),objetivo,1) print(lista) print(f'El elemento {objetivo} {"esta" if encontrado_lineal[0] else "no esta"} en la lista') print(f'El elemento {objetivo} {"esta" if encontrado_binario[0] else "no esta"} en la lista') print(f'Iteraciones Busqueda Lineal: {encontrado_lineal[1]}') print(f'Iteraciones Busqueda Binaria: {encontrado_binario[1]}') """ Salida De que tamano sera la lista?67 Que numero quieras encontrar?98 [0, 7, 11, 11, 14, 16, 17, 18, 18, 19, 19, 20, 20, 22, 23, 25, 26, 27, 29, 31, 33, 34, 37, 41, 41, 41, 41, 44, 44, 45, 46, 46, 49, 51, 51, 54, 56, 58, 59, 63, 64, 65, 65, 66, 66, 68, 68, 75, 76, 76, 78, 78, 79, 80, 82, 82, 83, 83, 84, 87, 89, 89, 90, 93, 93, 98, 100] El elemento 98 esta en la lista El elemento 98 esta en la lista Iteraciones Busqueda Lineal: 66 Iteraciones Busqueda Binaria: 6 """
Reto con busqueda binaria
import random import time contador = 0 def busqueda_binaria(lista, comienzo, final, objetivo): global contador if comienzo > final: return False medio = (comienzo + final) // 2 print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}') if lista[medio] == objetivo: contador = contador + 1 return True elif lista[medio] <= objetivo: contador = contador + 1 return busqueda_binaria(lista, medio +1, final, objetivo) elif lista[medio] >= objetivo: contador = contador + 1 return busqueda_binaria(lista, comienzo, medio - 1, objetivo) if __name__ == "__main__": tamano_de_lista = int(input('De que tamano sera la lista? : ')) objetivo = int(input('que numero quieres encontrar? : ')) contador = 0 lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)]) inicio = time.time() encontrado = busqueda_binaria(lista, 0, len(lista), objetivo) final = time.time() print(lista) print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista') print(f'La cantidad de pasos son: {contador + 1}') print(f'Se encontró en un tiempo de {(final - inicio)} ')```
No entiendo esta expresion, en que momento el comienzo podria ser mayor al final si siempre vale 0??
if comienzo > final: return False
No siempre es cero, cuando se encuentra el objetivo por arriba de la mitad de la lista, comienzo pasa a ser igual a medio +1.
si, volví a ver el vídeo y el valor de comienzo se actualiza de acuerdo al algoritmo, gracias,
