Mediana de dois vetores ordenados
Resolva o problema da mediana de dois vetores ordenados em O(log(min(m,n))) usando busca binária no limite de partição do vetor mais curto.
Mediana de dois vetores ordenados é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
A mediana de dois vetores ordenados
Mediana de dois vetores ordenados (LeetCode 4) é um problema clássico difícil. Dados dois vetores ordenados nums1 (de comprimento m) e nums2 (de comprimento n), encontre a mediana da sequência ordenada resultante da combinação dos dois em O(log(min(m,n))) de tempo. Uma abordagem ingênua intercala os dois vetores em O(m+n), mas a solução ideal usa busca binária nos limites das partições. Este é um dos problemas difíceis mais frequentes em entrevistas nas principais empresas de tecnologia.
# 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))Abordagem da intercalação ingênua
A abordagem mais simples, O(m+n): intercale os dois vetores ordenados e depois encontre a mediana. Intercalar dois vetores ordenados custa O(m+n). A mediana de um vetor de comprimento L é arr[L//2] se L for ímpar, ou (arr[L//2-1] + arr[L//2]) / 2 se L for par. Isso está correto, mas não atende ao requisito de O(log(min(m,n))). Em uma entrevista, sempre apresente essa abordagem primeiro para estabelecer uma referência e depois a otimize.
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.5A ideia da partição
A ideia principal: a mediana divide o vetor combinado em duas metades iguais. Precisamos encontrar uma partição de nums1 e uma partição de nums2 tais que: (1) As metades esquerdas tenham o mesmo tamanho total que as metades direitas. (2) Todos os elementos das metades esquerdas sejam ≤ todos os elementos das metades direitas. Se fizermos uma busca binária pelo ponto correto de partição em nums1, a partição em nums2 será determinada automaticamente pela restrição do comprimento 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])Busca binária na partição
Faça uma busca binária no índice de partição i de nums1 (o vetor mais curto). O índice de partição j em nums2 é determinado por j = (m+n+1)//2 - i, garantindo que as metades esquerdas tenham (m+n+1)//2 elementos. A partição é válida quando nums1[i-1] ≤ nums2[j] e nums2[j-1] ≤ nums1[i]. A busca binária ajusta i para cima ou para baixo até encontrar esse equilíbrio.
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.5Rastreando a busca binária
Rastreie nums1=[1,3], nums2=[2]: m=2, n=1, comprimento total=3, limite inferior=0 e limite superior=2. i=(0+2)//2=1 e j=(2+1+1)//2-1=1. O maior elemento à esquerda no primeiro vetor é 1, o menor elemento à direita no primeiro vetor é 3, o maior elemento à esquerda no segundo vetor é 2 e o menor elemento à direita no segundo vetor é infinito (j=1=n). Verificação: 1≤infinito e 2≤3 ✓. Como o total é ímpar, retorne o maior entre 1 e 2, que é 2,0. ✓ O algoritmo encontrou a partição na primeira etapa porque os tamanhos dos vetores são pequenos.
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 que fazer a busca binária no vetor mais curto
Fazemos a busca binária no vetor mais curto para obter O(log(min(m,n)), em vez de O(log(m+n)). A partição do vetor mais longo é totalmente determinada pela partição do vetor mais curto. Trocar as entradas quando len(nums1) > len(nums2) garante que o vetor mais curto seja sempre o espaço de busca. O invariante é: quando j é derivado de i e do comprimento total, j é sempre um índice de partição 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}')Lidando com comprimentos totais pares e ímpares
Quando o comprimento combinado é ímpar: a mediana é o maior elemento das metades esquerdas (max(max_left1, max_left2)). Quando é par: a mediana é a média entre o maior elemento das metades esquerdas e o menor elemento das metades direitas. A fórmula (m+n+1)//2 para o tamanho da metade esquerda funciona nos dois casos: para um total par, ela fornece n//2 (um elemento extra à esquerda), e calculamos a média com o menor elemento da direita para obter a mediana de um total 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 extremos
Casos extremos importantes: (1) Um vetor está vazio — a mediana do vetor não vazio. (2) Todos os elementos de um vetor são menores que os do outro — a partição fica em uma extremidade. (3) Elementos duplicados — o algoritmo lida com eles naturalmente. (4) Ambos os vetores têm comprimento 1 — mediana simples de dois elementos. Sempre teste esses casos depois de escrever o código. Os valores sentinela -∞ e +∞ tratam de forma adequada as partições nos limites (i=0 ou 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.5Generalização: k-ésimo menor em dois vetores
O problema da mediana pode ser generalizado para encontrar o k-ésimo menor elemento em dois vetores ordenados. A cada etapa, compare o k//2-ésimo elemento de cada vetor. Elimine a metade menor: esses k//2 elementos são todos menores que o k-ésimo elemento, portanto podemos descartá-los. Reduza k em k//2 e faça a chamada recursiva. Casos-base: um vetor vazio (retorne o k-ésimo elemento do vetor restante) ou k=1 (retorne o menor elemento entre os primeiros elementos dos dois vetores). Tempo: 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)}')Comparação de todas as abordagens
Comparação final: Mesclagem de matrizes: tempo O(m+n), espaço O(m+n). Pesquisa binária na partição: tempo O(log(min(m,n))), espaço O(1). Recursão do k-ésimo menor: tempo O(log(m+n)), pilha de chamadas O(log k). O método de partição com pesquisa binária é o que os entrevistadores esperam para este problema. É o problema comum mais difícil do LeetCode para explicar com clareza — pratique a lógica da partição e as quatro verificações de limites até que se tornem automáticas.
# 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')Estratégia de comunicação em entrevistas
Para este problema difícil em uma entrevista: (1) Apresente imediatamente a abordagem ingênua de mesclagem O(m+n) — isso demonstra competência. (2) Explique o objetivo O(log(min(m,n))) e a ideia da partição. (3) Percorra o invariante da partição: max_left1 ≤ min_right2 e max_left2 ≤ min_right1. (4) Trate explicitamente os valores sentinela. (5) Apresente a fórmula da mediana para quantidades ímpares e pares. (6) Faça testes com 1 ou 2 exemplos. Esta estrutura de 5 etapas demonstra uma resolução sistemática de problemas, mesmo em um problema que poucos candidatos conseguem resolver perfeitamente sob pressão.
# 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.5Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: a mediana de duas matrizes ordenadas pode ser encontrada em O(log(min(m,n))) realizando uma pesquisa binária pelo limite de partição correto na matriz mais curta; a partição é válida quando max_left1 ≤ min_right2 e max_left2 ≤ min_right1, com valores sentinela tratando os casos de limite; e a generalização do k-ésimo menor usa uma abordagem recursiva de eliminação pela metade em tempo O(log k). Parabéns por concluir as lições de Divisão e Conquista — agora você tem um conjunto abrangente de ferramentas para entrevistas de programação!
Perguntas Frequentes
A aula “Mediana de dois vetores ordenados” é grátis?
Sim — o texto completo de “Mediana de dois vetores ordenados” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Mediana de dois vetores ordenados”?
Resolva o problema da mediana de dois vetores ordenados em O(log(min(m,n))) usando busca binária no limite de partição do vetor mais curto. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Mediana de dois vetores ordenados”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Modelo de divisão e conquista
- Contar inversões usando ordenamento por intercalação modificado
- Elemento majoritário: votação de Boyer-Moore
- Mediana de dois vetores ordenados