def divide_y_conquista(problema): 
  """ Patrón general de Dividir y Conquistar """ 
  # Caso base: problema suficientemente pequeño 
  if es_simple(problema): return
  resolver_directamente(problema) 
  # DIVIDIR: Descomponer en subproblemas 
  subproblemas = dividir(problema) 
  # CONQUISTAR: Resolver recursivamente 
  soluciones_parciales = [] 
  for subproblema in subproblemas: 
    solucion = divide_y_conquista(subproblema) 
    soluciones_parciales.append(solucion)
  # COMBINAR: Fusionar soluciones 
  solucion_final = combinar(soluciones_parciales) 
  return solucion_final 

         Problema Original (tamaño n)
                    |
              [DIVIDIR]
                    |
      +-------------+-------------+
      |                           |
Subproblema 1              Subproblema 2
(tamaño n/2)               (tamaño n/2)
      |                           |
 [CONQUISTAR]               [CONQUISTAR]
 (recursivo)                (recursivo)
      |                           |
  Solución 1                 Solución 2
      |                           |
      +-------------+-------------+
                    |
               [COMBINAR]
                    |
             Solución Final

def busqueda_binaria(arr, objetivo, izq=0, der=None):
    """
    Búsqueda binaria recursiva
    Tiempo: O(log n)
    Espacio: O(log n) por la pila de recursión
    """
    if der is None:
        der = len(arr) - 1

    # Caso base: no encontrado
    if izq > der:
        return -1

    # DIVIDIR: Encontrar el punto medio
    mid = (izq + der) // 2

    # CONQUISTAR: ¿Es el elemento buscado?
    if arr[mid] == objetivo:
        return mid

    # CONQUISTAR (recursivo): Buscar en el subproblema apropiado
    if objetivo < arr[mid]:
        return busqueda_binaria(arr, objetivo, izq, mid - 1)
    else:
        return busqueda_binaria(arr, objetivo, mid + 1, der)

# Versión iterativa (más eficiente en espacio)
def busqueda_binaria_iterativa(arr, objetivo):
    """
    Búsqueda binaria iterativa
    Tiempo: O(log n)
    Espacio: O(1)
    """
    izq, der = 0, len(arr) - 1

    while izq <= der:
        mid = (izq + der) // 2

        if arr[mid] == objetivo:
            return mid
        elif objetivo < arr[mid]:
            der = mid - 1
        else:
            izq = mid + 1

    return -1

# Ejemplo
numeros = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]
print(busqueda_binaria(numeros, 23))  # Resultado: 5
print(busqueda_binaria(numeros, 100)) # Resultado: -1 (no encontrado)

def buscar_primero(arr, objetivo):
    """Encuentra la primera ocurrencia de objetivo"""
    izq, der = 0, len(arr) - 1
    resultado = -1
    
    while izq <= der:
        mid = (izq + der) // 2
        
        if arr[mid] == objetivo:
            resultado = mid
            der = mid - 1  # Continuar buscando a la izquierda
        elif objetivo < arr[mid]:
            der = mid - 1
        else:
            izq = mid + 1
    
    return resultado

def buscar_ultimo(arr, objetivo):
    """Encuentra la última ocurrencia de objetivo"""
    izq, der = 0, len(arr) - 1
    resultado = -1
    
    while izq <= der:
        mid = (izq + der) // 2
        
        if arr[mid] == objetivo:
            resultado = mid
            izq = mid + 1  # Continuar buscando a la derecha
        elif objetivo < arr[mid]:
            der = mid - 1
        else:
            izq = mid + 1
    
    return resultado

def contar_ocurrencias(arr, objetivo):
    """
    Cuenta las ocurrencias de objetivo en O(log n)
    """
    primero = buscar_primero(arr, objetivo)
    
    if primero == -1:
        return 0
    
    ultimo = buscar_ultimo(arr, objetivo)
    return ultimo - primero + 1

# Ejemplo

numeros = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
print(contar_ocurrencias(numeros, 2)) # 4
print(contar_ocurrencias(numeros, 8)) # 2
print(contar_ocurrencias(numeros, 5)) # 0

def karatsuba(x, y):
    """
    Multiplicación de Karatsuba
    Tiempo: O(n^1.585) donde n = número de dígitos
    """
    # Caso base
    if x < 10 or y < 10:
        return x * y

    # Calcular número de dígitos
    n = max(len(str(x)), len(str(y)))
    mitad = n // 2

    # DIVIDIR: Separar en mitades
    potencia = 10 ** mitad
    x_l = x // potencia  # Mitad izquierda de x
    x_r = x % potencia   # Mitad derecha de x
    y_l = y // potencia  # Mitad izquierda de y
    y_r = y % potencia   # Mitad derecha de y

    # CONQUISTAR: 3 multiplicaciones recursivas (¡no 4!)
    z0 = karatsuba(x_r, y_r)           # x_r * y_r
    z1 = karatsuba(x_l + x_r, y_l + y_r)  # (x_l + x_r)(y_l + y_r)
    z2 = karatsuba(x_l, y_l)           # x_l * y_l

    # COMBINAR
    # z1 - z2 - z0 = x_l*y_r + x_r*y_l (el término medio)
    return z2 * (10 ** (2 * mitad)) + (z1 - z2 - z0) * (10 ** mitad) + z0

# Ejemplo
x = 1234
y = 5678
print(f"Método estándar: {x * y}")
print(f"Karatsuba: {karatsuba(x, y)}")

# Para números grandes, la diferencia es notable
import time

# Número de 100 dígitos
grande_x = 12345678901234567890123456789012345678901234567890
grande_y = 98765432109876543210987654321098765432109876543210

inicio = time.time()
resultado_normal = grande_x * grande_y
tiempo_normal = time.time() - inicio

inicio = time.time()
resultado_karatsuba = karatsuba(grande_x, grande_y)
tiempo_karatsuba = time.time() - inicio

print(f"\nNúmeros de 50 dígitos:")
print(f"Método normal: {tiempo_normal:.6f}s")
print(f"Karatsuba: {tiempo_karatsuba:.6f}s")

# Búsqueda binaria - cada decisión depende de la anterior

def busqueda_binaria_no_paralelizable(arr, objetivo):
    izq, der = 0, len(arr) - 1

    # Paso 1: Verificar elemento central
    mid1 = (izq + der) // 2
    if arr[mid1] == objetivo:
        return mid1

    # Paso 2: DEPENDE del resultado del Paso 1
    # No puedo decidir dónde buscar hasta conocer arr[mid1]
    if objetivo < arr[mid1]:
        # Ahora busco en la izquierda
        der = mid1 - 1
    else:
        # Ahora busco en la derecha
        izq = mid1 + 1

    # Paso 3: DEPENDE del resultado del Paso 2
    # Y así sucesivamente...

    # ❌ No puedo ejecutar los pasos 1, 2 y 3 simultáneamente
    #    porque cada uno necesita el resultado del anterior

from concurrent.futures import ThreadPoolExecutor

def merge_sort_paralelo(arr, profundidad=0, max_profundidad=3):
    """
    Merge Sort con paralelismo limitado
    """
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    izquierda = arr[:mid]
    derecha = arr[mid:]

    # Solo paralelizar en los primeros niveles
    if profundidad < max_profundidad:
        with ThreadPoolExecutor(max_workers=2) as executor:
            # ✅ Estos dos pueden ejecutarse en paralelo
            futuro_izq = executor.submit(
                merge_sort_paralelo, izquierda, profundidad + 1, max_profundidad
            )
            futuro_der = executor.submit(
                merge_sort_paralelo, derecha, profundidad + 1, max_profundidad
            )

            izq_ordenada = futuro_izq.result()
            der_ordenada = futuro_der.result()
    else:
        # En niveles profundos, usar versión secuencial
        izq_ordenada = merge_sort_paralelo(izquierda, profundidad + 1, max_profundidad)
        der_ordenada = merge_sort_paralelo(derecha, profundidad + 1, max_profundidad)

    return merge(izq_ordenada, der_ordenada)

def quick_sort(arr):
    """
    Quick Sort usando Dividir y Conquistar
    Promedio: O(n log n)
    Peor caso: O(n²)
    """
    if len(arr) <= 1:
        return arr
    
    # DIVIDIR: Elegir pivote y particionar
    pivote = arr[len(arr) // 2]
    menores = [x for x in arr if x < pivote]
    iguales = [x for x in arr if x == pivote]
    mayores = [x for x in arr if x > pivote]
    
    # CONQUISTAR: Ordenar recursivamente
    menores_ordenados = quick_sort(menores)
    mayores_ordenados = quick_sort(mayores)
    
    # COMBINAR: Concatenar (trivial)
    return menores_ordenados + iguales + mayores_ordenados

# Ejemplo

numeros = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(numeros))