Mediana de dos arrays ordenados
Resuelva median-of-two-sorted-arrays en O(log(min(m,n))) mediante búsqueda binaria en el límite de partición del array más corto.
Mediana de dos arrays ordenados es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
La mediana de dos arrays ordenados
Mediana de dos arrays ordenados (LeetCode 4) es un problema clásico de dificultad alta. Dados dos arrays ordenados nums1 (de longitud m) y nums2 (de longitud n), encuentre la mediana de su secuencia ordenada combinada en tiempo O(log(min(m,n))). Un enfoque ingenuo combina ambos arrays en O(m+n), pero la solución óptima utiliza búsqueda binaria sobre los límites de partición. Este es uno de los problemas difíciles más frecuentes en las principales empresas tecnológicas.
# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0
nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5
print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))Enfoque ingenuo de combinación
El enfoque más sencillo, O(m+n): combine ambos arrays ordenados y, después, encuentre la mediana. Combinar dos arrays ordenados cuesta O(m+n). La mediana de un array de longitud L es arr[L//2] si L es impar, o (arr[L//2-1] + arr[L//2]) / 2 si L es par. Esto es correcto, pero no cumple el requisito O(log(min(m,n))). Presente siempre este enfoque primero en una entrevista para establecer una referencia y, después, optimícelo.
def find_median_naive(nums1, nums2):
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i]); i += 1
else:
merged.append(nums2[j]); j += 1
merged += nums1[i:] + nums2[j:]
L = len(merged)
if L % 2 == 1:
return float(merged[L // 2])
return (merged[L//2 - 1] + merged[L//2]) / 2.0
print(find_median_naive([1,3],[2])) # 2.0
print(find_median_naive([1,2],[3,4])) # 2.5La idea de la partición
La idea clave: la mediana divide el array combinado en dos mitades iguales. Necesitamos encontrar una partición de nums1 y otra de nums2 tales que: (1) Las mitades izquierdas tengan el mismo tamaño total que las mitades derechas. (2) Todos los elementos de las mitades izquierdas sean ≤ todos los elementos de las mitades derechas. Si hacemos una búsqueda binaria para encontrar el punto de partición adecuado en nums1, la partición en nums2 queda determinada automáticamente por la restricción de longitud total.
# Partition concept visualised:
# nums1: [1, 3] | [5, 7] (partition after index 1)
# nums2: [2, 4] | [6, 8] (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5
nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])Búsqueda binaria sobre la partición
Realice una búsqueda binaria sobre el índice de partición i de nums1 (el array más corto). El índice de partición j en nums2 queda determinado como j = (m+n+1)//2 - i (lo que garantiza que las mitades izquierdas tengan (m+n+1)//2 elementos). La partición es válida cuando nums1[i-1] ≤ nums2[j] y nums2[j-1] ≤ nums1[i]. La búsqueda binaria ajusta i hacia arriba o hacia abajo hasta encontrar este equilibrio.
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is the shorter array
if len(nums1) > len(nums2):
return find_median_sorted_arrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # partition index in nums1
j = (m + n + 1) // 2 - i # partition index in nums2
# Boundary values with sentinels
max_left1 = float('-inf') if i == 0 else nums1[i-1]
min_right1 = float('inf') if i == m else nums1[i]
max_left2 = float('-inf') if j == 0 else nums2[j-1]
min_right2 = float('inf') if j == n else nums2[j]
if max_left1 <= min_right2 and max_left2 <= min_right1:
# Found the correct partition
if (m + n) % 2 == 1:
return float(max(max_left1, max_left2))
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
elif max_left1 > min_right2:
hi = i - 1 # i is too large, move left
else:
lo = i + 1 # i is too small, move right
return 0.0
print(find_median_sorted_arrays([1,3],[2])) # 2.0
print(find_median_sorted_arrays([1,2],[3,4])) # 2.5Seguimiento de la búsqueda binaria
Siga nums1=[1,3], nums2=[2]: m=2, n=1, total=3, lo=0, hi=2. i=(0+2)//2=1, j=(2+1+1)//2-1=1. max_left1=nums1[0]=1, min_right1=nums1[1]=3, max_left2=nums2[0]=2, min_right2=inf (j=1=n). Comprobación: 1≤inf y 2≤3 ✓. Total impar: return max(1,2)=2.0. ✓ El algoritmo encontró la partición en el primer paso porque los tamaños de los arrays son pequeños.
def find_median_traced(nums1, nums2):
if len(nums1) > len(nums2):
return find_median_traced(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
step = 0
while lo <= hi:
step += 1
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
ml1 = float('-inf') if i==0 else nums1[i-1]
mr1 = float('inf') if i==m else nums1[i]
ml2 = float('-inf') if j==0 else nums2[j-1]
mr2 = float('inf') if j==n else nums2[j]
print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
print(find_median_traced([1,3],[2]))Por qué se realiza la búsqueda binaria sobre el array más corto
Realizamos la búsqueda binaria sobre el array más corto para lograr O(log(min(m,n))) en lugar de O(log(m+n)). La partición del array más largo queda completamente determinada por la partición del array más corto. Intercambiar las entradas si len(nums1) > len(nums2) garantiza que el array más corto sea siempre el espacio de búsqueda. La invariante es que, cuando j se obtiene a partir de i y de la longitud total, j siempre es un índice de partición válido para nums2.
# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)
m, n = 3, 5 # m <= n
half = (m+n+1)//2
for i in range(m+1):
j = half - i
valid = 0 <= j <= n
print(f'i={i}: j={j}, valid={valid}')Gestión de longitudes totales pares e impares
Cuando la longitud combinada es impar: la mediana es el máximo de las mitades izquierdas (max(max_left1, max_left2)). Cuando es par: la mediana es el promedio del máximo de las mitades izquierdas y el mínimo de las mitades derechas. La fórmula (m+n+1)//2 para el tamaño de la mitad izquierda funciona en ambos casos: para un total par produce n//2 (un elemento adicional a la izquierda), y calculamos el promedio con min_right para obtener la mediana de un conjunto par.
def median_demo(a, b):
merged = sorted(a + b)
L = len(merged)
expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
computed = find_median_sorted_arrays(a[:], b[:])
print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
assert abs(expected - computed) < 1e-9
def find_median_sorted_arrays(nums1, nums2):
if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
m,n=len(nums1),len(nums2); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[]) # single arrayCasos límite
Casos límite importantes: (1) Un array está vacío: la mediana del array no vacío. (2) Todos los elementos de un array son menores que los del otro: la partición se sitúa en un extremo. (3) Elementos duplicados: el algoritmo los gestiona de forma natural. (4) Ambos arrays tienen longitud 1: mediana sencilla de dos elementos. Pruebe siempre estos casos después de escribir el código. Los valores centinela -∞ y +∞ gestionan correctamente las particiones en los límites (i=0 o i=m).
def fmsa(a,b):
if len(a)>len(b): return fmsa(b,a)
m,n=len(a),len(b); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
# Edge cases
print(fmsa([], [1])) # 1.0
print(fmsa([2], [])) # 2.0
print(fmsa([1,2], [3,4])) # 2.5
print(fmsa([3,4], [1,2])) # 2.5
print(fmsa([1,1,1], [1,1])) # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35])) # 17.5Generalización: k-ésimo menor en dos arrays
El problema de la mediana se generaliza para encontrar el k-ésimo elemento menor entre dos arrays ordenados. En cada paso, compare el elemento situado en la posición k//2 de cada array. Elimine la mitad menor: esos k//2 elementos son todos menores que el k-ésimo elemento, por lo que puede descartarlos. Reduzca k en k//2 y repita el proceso. Casos base: un array vacío (devuelva el k-ésimo elemento del restante) o k=1 (devuelva el mínimo de los primeros elementos de ambos). Tiempo: O(log k) = O(log(m+n)).
def kth_smallest(nums1, nums2, k):
if not nums1: return nums2[k-1]
if not nums2: return nums1[k-1]
if k == 1: return min(nums1[0], nums2[0])
# Compare k//2-th elements
half = k // 2
i = min(half, len(nums1)) - 1 # index in nums1
j = min(half, len(nums2)) - 1 # index in nums2
if nums1[i] <= nums2[j]:
# Eliminate first (i+1) elements of nums1
return kth_smallest(nums1[i+1:], nums2, k - (i+1))
else:
return kth_smallest(nums1, nums2[j+1:], k - (j+1))
nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')Comparación de todos los enfoques
Comparación final: Combinar arrays: O(m+n) de tiempo, O(m+n) de espacio. Búsqueda binaria sobre la partición: O(log(min(m,n))) de tiempo, O(1) de espacio. Recursión para el k-ésimo menor: O(log(m+n)) de tiempo, O(log k) en la pila de llamadas. El método de partición con búsqueda binaria es el que los entrevistadores esperan para este problema. Es el problema común de LeetCode más difícil de explicar con claridad; practique la lógica de partición y las cuatro comprobaciones de límites hasta hacerlas automáticamente.
# Performance comparison
import time, random
def merge_median(a, b):
merged = sorted(a+b)
L=len(merged)
return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
def binary_median(a, b):
if len(a)>len(b): return binary_median(b,a)
m,n=len(a),len(b);lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2;j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
for size in [100, 10000]:
a = sorted(random.sample(range(size*2), size))
b = sorted(random.sample(range(size*2), size))
t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')Estrategia de comunicación en entrevistas
Para este problema difícil en una entrevista: (1) exponga inmediatamente el enfoque ingenuo de combinación en O(m+n); demuestra competencia. (2) Explique el objetivo de O(log(min(m,n))) y la idea de la partición. (3) Repase el invariante de la partición: max_left1 ≤ min_right2 y max_left2 ≤ min_right1. (4) Gestione explícitamente los valores centinela. (5) Indique la fórmula de la mediana para los casos impares y pares. (6) Compruebe la solución con 1 o 2 ejemplos. Este marco de 5 pasos demuestra una resolución sistemática de problemas incluso ante un problema que pocos candidatos resuelven perfectamente bajo presión.
# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
return findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
max_l1 = nums1[i-1] if i > 0 else float('-inf')
min_r1 = nums1[i] if i < m else float('inf')
max_l2 = nums2[j-1] if j > 0 else float('-inf')
min_r2 = nums2[j] if j < n else float('inf')
if max_l1 <= min_r2 and max_l2 <= min_r1:
if (m + n) % 2:
return float(max(max_l1, max_l2))
return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
elif max_l1 > min_r2: hi = i - 1
else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2])) # 2.0
print(findMedianSortedArrays([1,2],[3,4])) # 2.5Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: la mediana de dos arrays ordenados se puede encontrar en O(log(min(m,n))) mediante una búsqueda binaria del límite de partición correcto en el array más corto; la partición es válida cuando max_left1 ≤ min_right2 y max_left2 ≤ min_right1, con valores centinela para gestionar los casos límite; y la generalización del k-ésimo menor utiliza un enfoque recursivo de eliminación de la mitad en O(log k) de tiempo. ¡Enhorabuena por completar las lecciones de Divide and Conquer! Ahora dispone de un conjunto completo de herramientas para las entrevistas de programación.
Preguntas frecuentes
¿La lección «Mediana de dos arrays ordenados» es gratis?
Sí — el texto completo de «Mediana de dos arrays ordenados» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Mediana de dos arrays ordenados»?
Resuelva median-of-two-sorted-arrays en O(log(min(m,n))) mediante búsqueda binaria en el límite de partición del array más corto. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Mediana de dos arrays ordenados»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Plantilla de divide y vencerás
- Contar inversiones con merge sort modificado
- Elemento mayoritario: votación de Boyer-Moore
- Mediana de dos arrays ordenados