Algoritmos de Búsqueda O(log n) vs O(n) en Python

Comparación de algoritmos de búsqueda: O(n) frente a O(log n) para desarrolladores

En arrays con millones de elementos, la búsqueda lineal puede requerir hasta 10 millones de operaciones, mientras que la búsqueda binaria se resuelve en tan solo 24 comparaciones. Analizamos cuatro algoritmos de búsqueda en Python, cubriendo complejidad temporal, compromisos prácticos y recomendaciones claras para elegir el adecuado en entornos reales. Incluye implementaciones seguras ante desbordamiento, funciones lower_bound/upper_bound y ejemplos listos para LeetCode.

El problema de búsqueda: dado un conjunto arr, encontrar el índice de target, o devolver -1. El conjunto puede estar ordenado o desordenado, ser estático o dinámico. Casos reales incluyen la consulta de SKUs en e-commerce (millones de referencias) y la validación de identificadores de transacción en fintech.

Búsqueda lineal para datos desordenados

Funciona con cualquier colección. Revisa los elementos secuencialmente.

Implementación:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Complejidad:

• Tiempo: O(n) en el peor caso y promedio, O(1) en el mejor caso.
• Espacio: O(1).

Búsqueda binaria y sus variantes

Requiere un array ordenado. Divide repetidamente el intervalo de búsqueda por la mitad.

Implementación iterativa: Usa mid = left + (right - left) // 2 para evitar desbordamientos enteros (crítico en C++/Java; seguro e idiomático también en Python).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Ejemplo
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5))  # 3
print(lower_bound(sorted_arr, 3))     # 1
print(upper_bound(sorted_arr, 3))     # 3

Complejidad: Tiempo O(log n), espacio O(1).

lower_bound devuelve la posición de inserción más a la izquierda para target; upper_bound, la más a la derecha. Esenciales para manejar duplicados y resolver problemas de LeetCode como «Buscar primera y última posición de un elemento en un array ordenado».

Búsqueda exponencial para flujos de datos o tamaños desconocidos

Ideal para arrays ordenados de longitud desconocida —o cuando target probablemente esté cerca del inicio—. Primero identifica un rango acotado mediante crecimiento exponencial y luego aplica búsqueda binaria.

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Ejemplo
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456))  # 123456

Complejidad: O(log i), donde i es el índice del objetivo; en el peor caso, O(log n); espacio O(1).

Búsqueda basada en hash para colecciones dinámicas

Búsqueda promedio en O(1) usando tablas hash (set/dict en Python).

def hash_search_set(arr, target):
    s = set(arr)
    return target in s

def hash_search_dict(pairs, key):
    d = dict(pairs)
    return d.get(key)

# Ejemplo
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30))  # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b"))  # 2

Complejidad: O(1) en promedio, O(n) en el peor caso (colisiones de hash), espacio O(n).

Guía para seleccionar el algoritmo adecuado

• Array desordenado: Búsqueda lineal si N < 100 o las búsquedas son poco frecuentes.
• Datos ordenados y estáticos: Búsqueda binaria.
• Datos dinámicos con inserciones frecuentes: Tabla hash (si no importa el orden).
• Flujos de datos o tamaños desconocidos: Búsqueda exponencial.

| Algoritmo | Tiempo promedio | Tiempo peor | Espacio | Requisitos |

|-----------|-----------------|-------------|---------|------------|

| Lineal | O(n) | O(n) | O(1) | Cualquiera |

| Binaria | O(log n) | O(log n) | O(1) | Ordenado |

| Exponencial | O(log i) | O(log n) | O(1) | Ordenado |

| Hash | O(1) | O(n) | O(n) | Claves hasheables |

Conclusiones clave

• Para 10 millones de elementos: la búsqueda binaria requiere ~24 comparaciones frente a 10 millones en la lineal.
• Siempre prefiere el cálculo seguro de mid en búsquedas binarias —incluso en Python, es un hábito robusto y profesional.
• Las tablas hash intercambian memoria (O(n)) por búsquedas ultrarrápidas en promedio (O(1)).
• lower_bound y upper_bound son indispensables para gestionar duplicados y lógica de inserción.
• La búsqueda exponencial brilla cuando los objetivos suelen agruparse al principio de arrays ordenados masivos.

— Editorial Team