La búsqueda binaria es un algoritmo eficiente que se basa en el principio de "divide y vencerás". Permite encontrar elementos en listas ordenadas mucho más rápido que una búsqueda lineal. A través de iteraciones, el problema se va reduciendo hasta llegar a la solución o determinar que el elemento no está presente. Este enfoque se llama binario porque la lista se divide siempre en dos partes.
¿Cuáles son las características esenciales de la búsqueda binaria?
Para que la búsqueda binaria sea efectiva, debemos tener en cuenta lo siguiente:
Lista ordenada: El algoritmo asume que la lista ya está ordenada.
División iterativa: En cada paso, la lista se divide en dos, descartando la mitad que no contiene el objetivo.
Eficiencia: Es mucho más eficiente que una búsqueda lineal, especialmente en listas grandes, pero requiere un estado ordenado previo de la lista.
¿Cómo funciona frente a la búsqueda lineal?
Búsqueda lineal: Se recorre elemento por elemento hasta encontrar el objetivo o alcanzar el final de la lista. Es útil cuando la lista no está ordenada y se busca un solo elemento.
Búsqueda binaria: Reduce significativamente el número de verificaciones necesarias. En cada paso, descarta la mitad de la lista. Por ejemplo, si se tiene una lista de 100 elementos y está ordenada, el algoritmo probablemente encontrará un elemento en muy pocos pasos, en comparación con una búsqueda lineal que podría necesitar hasta 100 pasos.
¿Cómo implementar la búsqueda binaria recursiva?
Implemetar la búsqueda binaria de forma recursiva es un ejercicio interesante que demuestra el poder de los algoritmos eficientes en manejar grandes conjuntos de datos. Aquí hay un ejemplo del código en Python:
defbusqueda_binaria(lista, objetivo, inicio, final):if inicio > final:returnFalse medio =(inicio + final)//2if lista[medio]== objetivo:returnTrueelif lista[medio]< objetivo:return busqueda_binaria(lista, objetivo, medio +1, final)else:return busqueda_binaria(lista, objetivo, inicio, medio -1)# Ejemplo de usolista =[1,3,5,7,9,11,13,15,17,19]objetivo =13print(busqueda_binaria(lista, objetivo,0,len(lista)-1))# Salida -> True
Pasos del algoritmo
Condición de parada: Si el índice de inicio es mayor que el índice de final, el objetivo no está presente.
Calcular el punto medio: Utiliza (inicio + final) // 2.
Comparaciones:
Si el elemento en el medio es el objetivo, devuelve True.
Si el medio es menor, busca en la sublista de la derecha.
Si el medio es mayor, busca en la sublista de la izquierda.
¿Qué considerar para usar la búsqueda binaria?
Antes de decidir entre una búsqueda lineal o binaria, ten en cuenta:
Reordenamiento de la lista: Si planeas realizar varias búsquedas en la misma lista, podría valer la pena ordenarla una vez e implementar la búsqueda binaria.
Costo de ordenamiento vs. búsqueda: Puedes amortizar el costo de ordenar una lista si esto reduce significativamente el tiempo requerido para búsquedas repetitivas.
Este equilibrio entre el tiempo de procesamiento y el uso de memoria permitirá implementar la solución más adecuada para tu caso.
Dominando la búsqueda binaria: Más allá del algoritmo
La búsqueda binaria no solo es un ejercicio de programación, sino una introducción a la optimización de algoritmos en tiempo y espacio. Aquí hay algunos consejos prácticos:
Serializa y guarda estados intermedios: Para listas grandes, considerar guardar el estado ordenado y usarlo en búsquedas subsiguientes.
Prueba y error: Usa contadores o procesos de debug para medir la eficiencia y ajustar la lógica según los datos específicos.
Codificación recursiva vs. iterativa: Ambas tienen sus pros y contras; elige la que mejor se adapte a tu comodidad y los requerimientos del problema.
Reto adicional
Intenta implementar un contador que mida cuántas veces se ejecutan las iteraciones en los algoritmos de búsqueda lineal y binaria. Esto te permitirá entender mejor el impacto de las distintas estrategias de búsqueda a medida que aumentas el tamaño de la lista. Únete a la discusión y comparte tus resultados para seguir aprendiendo y optimizando.
La búsqueda binaria es un algoritmo eficiente que se basa en el principio de "divide y vencerás". Permite encontrar elementos en listas ordenadas mucho más rápido que una búsqueda lineal. A través de iteraciones, el problema se va reduciendo hasta llegar a la solución o determinar que el elemento no está presente. Este enfoque se llama binario porque la lista se divide siempre en dos partes.
¿Cuáles son las características esenciales de la búsqueda binaria?
Para que la búsqueda binaria sea efectiva, debemos tener en cuenta lo siguiente:
Lista ordenada: El algoritmo asume que la lista ya está ordenada.
División iterativa: En cada paso, la lista se divide en dos, descartando la mitad que no contiene el objetivo.
Eficiencia: Es mucho más eficiente que una búsqueda lineal, especialmente en listas grandes, pero requiere un estado ordenado previo de la lista.
¿Cómo funciona frente a la búsqueda lineal?
Búsqueda lineal: Se recorre elemento por elemento hasta encontrar el objetivo o alcanzar el final de la lista. Es útil cuando la lista no está ordenada y se busca un solo elemento.
Búsqueda binaria: Reduce significativamente el número de verificaciones necesarias. En cada paso, descarta la mitad de la lista. Por ejemplo, si se tiene una lista de 100 elementos y está ordenada, el algoritmo probablemente encontrará un elemento en muy pocos pasos, en comparación con una búsqueda lineal que podría necesitar hasta 100 pasos.
¿Cómo implementar la búsqueda binaria recursiva?
Implemetar la búsqueda binaria de forma recursiva es un ejercicio interesante que demuestra el poder de los algoritmos eficientes en manejar grandes conjuntos de datos. Aquí hay un ejemplo del código en Python:
def busqueda_binaria(lista, objetivo, inicio, final):
if inicio > final:
return False
medio = (inicio + final) // 2
if lista[medio] == objetivo:
return True
elif lista[medio] < objetivo:
return busqueda_binaria(lista, objetivo, medio + 1, final)
else:
return busqueda_binaria(lista, objetivo, inicio, medio - 1)
# Ejemplo de uso
lista = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
objetivo = 13
print(busqueda_binaria(lista, objetivo, 0, len(lista) - 1)) # Salida -> True
Pasos del algoritmo
Condición de parada: Si el índice de inicio es mayor que el índice de final, el objetivo no está presente.
Calcular el punto medio: Utiliza (inicio + final) // 2.
Comparaciones:
Si el elemento en el medio es el objetivo, devuelve True.
Si el medio es menor, busca en la sublista de la derecha.
Si el medio es mayor, busca en la sublista de la izquierda.
¿Qué considerar para usar la búsqueda binaria?
Antes de decidir entre una búsqueda lineal o binaria, ten en cuenta:
Reordenamiento de la lista: Si planeas realizar varias búsquedas en la misma lista, podría valer la pena ordenarla una vez e implementar la búsqueda binaria.
Costo de ordenamiento vs. búsqueda: Puedes amortizar el costo de ordenar una lista si esto reduce significativamente el tiempo requerido para búsquedas repetitivas.
Este equilibrio entre el tiempo de procesamiento y el uso de memoria permitirá implementar la solución más adecuada para tu caso.
Dominando la búsqueda binaria: Más allá del algoritmo
La búsqueda binaria no solo es un ejercicio de programación, sino una introducción a la optimización de algoritmos en tiempo y espacio. Aquí hay algunos consejos prácticos:
Serializa y guarda estados intermedios: Para listas grandes, considerar guardar el estado ordenado y usarlo en búsquedas subsiguientes.
Prueba y error: Usa contadores o procesos de debug para medir la eficiencia y ajustar la lógica según los datos específicos.
Codificación recursiva vs. iterativa: Ambas tienen sus pros y contras; elige la que mejor se adapte a tu comodidad y los requerimientos del problema.
Reto adicional
Intenta implementar un contador que mida cuántas veces se ejecutan las iteraciones en los algoritmos de búsqueda lineal y binaria. Esto te permitirá entender mejor el impacto de las distintas estrategias de búsqueda a medida que aumentas el tamaño de la lista. Únete a la discusión y comparte tus resultados para seguir aprendiendo y optimizando.
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
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')
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.