Búsqueda binaria recursiva

3.1 Principio de funcionamiento de la búsqueda binaria recursiva

La búsqueda binaria es un algoritmo para encontrar un elemento en un arreglo ordenado que funciona bajo el principio de "divide y vencerás". Compara el elemento buscado con el elemento en medio del arreglo y decide en qué mitad del arreglo seguir buscando. La búsqueda binaria recursiva repite este proceso llamándose a sí misma con los límites actualizados del arreglo.

Pasos del algoritmo:

1. Comparamos el elemento buscado con el elemento en medio del arreglo.
2. Si el elemento en medio coincide con el buscado, devolvemos su índice.
3. Si el elemento buscado es menor, repetimos la búsqueda en la mitad izquierda del arreglo.
4. Si el elemento buscado es mayor, repetimos la búsqueda en la mitad derecha del arreglo.
5. Repetimos el proceso hasta encontrar el elemento o agotar el arreglo.

Implementación de la búsqueda binaria recursiva

Ejemplo en Python:

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Caso base: elemento no encontrado
            
    mid = (left + right) // 2  # Encontramos el medio del arreglo
            
    if arr[mid] == target:
        return mid  # Caso base: elemento encontrado
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # Buscamos en la mitad derecha
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # Buscamos en la mitad izquierda
        
# Ejemplo de uso:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Elemento encontrado en la posición: {result}")  # Imprimirá: Elemento encontrado en la posición: 6
        

3.2 Comparación con la búsqueda binaria iterativa

Búsqueda binaria iterativa:

def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
            
    while left <= right:
        mid = (left + right) // 2
                
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # Elemento no encontrado
        
# Ejemplo de uso:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)
print(f"Elemento encontrado en la posición: {result}")  # Imprimirá: Elemento encontrado en la posición: 6
        

Comparación:

Simplicidad de implementación:

• El algoritmo recursivo suele ser más simple y corto, pero requiere entender las llamadas recursivas.
• El algoritmo iterativo usa un bucle, lo cual puede ser más sencillo para programadores principiantes.

Memoria:

• El algoritmo recursivo usa la pila de llamadas, lo que puede causar un incremento en el uso de memoria con arreglos grandes.
• El algoritmo iterativo usa una cantidad constante de memoria, lo que lo hace más eficiente en términos de uso de memoria.

Rendimiento:

• Ambos algoritmos tienen una complejidad temporal de O(log n).
• El algoritmo recursivo puede ser más lento debido al overhead de las llamadas recursivas, especialmente si la profundidad de la recursión es grande.

3.3 Ejemplos de problemas para la búsqueda binaria recursiva

La búsqueda binaria recursiva es un algoritmo poderoso que ayuda a encontrar rápidamente elementos en arreglos ordenados. Se basa en el principio de "divide y vencerás" y utiliza la recursión para dividir la tarea en sub-tareas más pequeñas.

La comparación de los enfoques recursivo e iterativo muestra que cada uno de ellos tiene sus ventajas y desventajas dependiendo del problema específico. Comprender estos algoritmos y su aplicación permite resolver eficientemente problemas de búsqueda en programación.

Por ejemplo, tales como:

Búsqueda de un elemento en un arreglo ordenado:

Búsqueda de un elemento específico en un arreglo de números, como la evaluación de pruebas, búsqueda en una base de datos por claves ordenadas, etc.

Verificación de presencia de un elemento:

Verificación de si un valor específico está presente en una lista de usuarios permitidos, identificadores, etc.

Búsqueda del valor más cercano:

Búsqueda del elemento más cercano a un valor dado en un arreglo, como cuando se busca la tienda más cercana, la estación, etc.

Optimización:

Resolución de problemas que requieren encontrar el valor óptimo en un arreglo ordenado, como encontrar el punto de mínimo o máximo en funciones.