Recursive Searching and Sorting
Introduzido| English | Significado |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | dividir e conquer |
| merge sort/mɜːdʒ sɔːt/ | ordenação por fusão |
| merge/mɜːdʒ/ | fusão |
Recursão encontra busca e ordenação
- A mesma ideia divide-and-conquer 分治 impulsiona a busca binária recursiva e o merge sort 归并排序.
- Divida o problema ao meio, resolva as metades, combine.
- Busca binária recursiva busca uma metade chamando a si mesma nela.
- Merge sort ordena cada metade e depois mescla as metades ordenadas juntas.
Busca binária recursiva
- Caso base: um intervalo vazio significa que o alvo não foi encontrado.
- Olhe para o meio. Se for o alvo, retorne seu índice.
- Se o alvo for menor, recurse na metade esquerda; se maior, na metade direita.
- Cada chamada reduz o intervalo pela metade — o mesmo
O(log n), escrito de forma recursiva.
Merge sort
- Divida o array em duas metades; ordene cada metade recursivamente.
- Caso base: um array com 0 ou 1 elemento já está ordenado.
- Mesclar: percorra ambas as metades ordenadas, sempre pegando o menor elemento da frente.
- Muito mais rápido que os sorts
n²— cerca den log ntrabalho.
Por que dividir-e-conquistar vence
- Dividir o problema ao meio a cada passo dá o fator
log n. - O
n log ndo merge sort supera o selection/insertion sort'sn²em grandes arrays. - O caso base (vazio ou um elemento) interrompe todos os ramos.
- Mesma estrutura de toda recursão: divida para baixo, combine para cima.
A busca binária recursiva recursiona em UMA metade (o alvo está apenas de um lado); o merge sort recursiona em AMBAS as metades e depois as mescla. Ambos precisam de um caso base — um intervalo vazio significa "não encontrado" para a busca; um array com 0 ou 1 elemento já está ordenado para o merge sort. Dividir-e-conquistar é o que os torna rápidos (O(log n) e O(n log n)).
Ordenando com merge sort [3, 1, 2, 4]:
- Divida em
[3, 1]e[2, 4]; ordene cada →[1, 3]e[2, 4]. - Mesclagem: pegue 1, depois 2, depois 3, depois 4 →
[1, 2, 3, 4]. - Cada mesclagem escolhe o menor elemento da frente por vez.
Busca binária recursiva recorre sobre um meio (caso base: intervalo vazio = não encontrado) para O(log n) busca. Merge sort recorre sobre ambas as metades e combina elas (caso base: 0 ou 1 elemento) para O(n log n) ordenação. Ambos são divide-and-conquer: dividir para baixo, combinar de volta para cima — muito mais rápido que n².
Merge sort splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The target is only on one side of the middle.
Merge sort recurses on...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
One (or zero) element needs no sorting.
Merge sort's running time is about...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Always take the smaller front element: 1, 2, 3, 4.