Implementar búsqueda binaria en Python es más simple de lo que parece. Aquí verás cómo construir una función recursiva clara, preparar una lista ordenada con random y list comprehension, y gestionar el punto de entrada del programa. Todo con buenas prácticas y explicaciones directas.
¿Cómo preparar el entorno en Python para binary search?
Antes de codificar, se crea un archivo y se define el punto de ingreso con el keyword if name == "main". Luego, se generan datos aleatorios y se ordenan, porque la búsqueda binaria requiere una lista previamente ordenada.
- Crear el archivo y definir el punto de entrada.
- Importar el módulo random.
- Generar 10 números entre 0 y 100 con list comprehension.
- Ordenar la lista con sort para modificarla en sitio.
- Imprimir los datos como guía visual.
¿Cómo generar y ordenar datos con random y list comprehension?
Se evita escribir un for loop manual usando list comprehension. La lista se ordena con sort; recuerda que sort modifica la lista y sorted crea una nueva.
import random
if __name__ == "__main__":
data = [random.randrange(0, 100) for _ in range(10)]
data.sort()
print("Datos ordenados:", data)
¿Qué diferencia hay entre sort y sorted?
- sort: ordena en el lugar y no devuelve una nueva lista.
- sorted: devuelve una copia ordenada y no altera la original.
Usar sort aquí simplifica el flujo y garantiza que la estructura requerida por el algoritmo esté lista.
¿Cómo se define la función recursiva binary search en Python?
La interfaz establece el contrato: recibe la lista ordenada, el target y dos índices, low y high, que representan el estado actual de búsqueda. Devuelve True si encuentra el elemento y False si no.
¿Cuál es la interfaz y el caso base?
El caso base valida si low > high: significa que se recorrió todo el rango posible y el número no está en la lista. Se evita así un error de fuera de índice y se detiene la recursión.
def binary_search(data, target, low, high):
if low > high:
return False
# se completará más abajo
¿Cómo calcular el índice medio y decidir los tres casos?
Se calcula el índice medio con división entera: mid = (low + high) // 2. Luego se evalúan tres escenarios:
- Igualdad: target == data[mid] → encontrado.
- Menor: target < data[mid] → buscar en la mitad izquierda: high = mid - 1.
- Mayor: en el lado derecho: low = mid + 1.
def binary_search(data, target, low, high):
if low > high:
return False
mid = (low + high) // 2
if target == data[mid]:
return True
elif target < data[mid]:
return binary_search(data, target, low, mid - 1)
else:
return binary_search(data, target, mid + 1, high)
¿Cómo ejecutar el script y qué reto propone el instructor?
Tras ordenar, se pide al usuario el número a buscar con input y se convierte a entero con int, ya que input devuelve cadenas. El resultado se imprime indicando si se encontró o no. En pruebas, se vieron casos donde el número sí está y otros donde no está, validando la implementación.
¿Cómo interactúa el usuario con input y conversión a int?
Se captura el objetivo y se llama a la función con índices correctos: low = 0 y high = len(data) - 1.
if __name__ == "__main__":
data = [random.randrange(0, 100) for _ in range(10)]
data.sort()
print("Datos ordenados:", data)
target = int(input("What number would you like to find? "))
found = binary_search(data, target, 0, len(data) - 1)
print(found)
¿Qué ejercicio extra se sugiere sin recursión?
Se propone implementar la misma lógica sin recursión, usando ciclos para actualizar low y high. Es un gran ejercicio para reforzar el manejo de estado, comparaciones y división entera.
¿Te animas a compartir tu versión iterativa con ciclos y contar qué decisiones tomaste al actualizar los índices?
