Implementar búsqueda binaria recursiva en Python

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?