Recursive Searching and Sorting · Busca Recursiva e Ordenação
| English | Português |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | dividir e conquistar |
| merge sort/mɜːdʒ sɔːt/ | ordenação por fusão |
| merge/mɜːdʒ/ | mesclar-se |
Recursion meets search and sort
- The same divide-and-conquer 分治 idea powers recursive binary search and merge sort 归并排序.
- Split the problem in half, solve the halves, combine.
- Recursive binary search searches one half by calling itself on it.
- Merge sort sorts each half, then merges the sorted halves together.
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.
Recursive binary search
- Base case: an empty range means the target is not found.
- Look at the middle. If it's the target, return its index.
- If the target is smaller, recurse on the left half; if larger, the right half.
- Each call halves the range — the same
O(log n), written recursively.
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
- Split the array into two halves; sort each half recursively.
- Base case: an array of 0 or 1 element is already sorted.
- Merge 合并: walk both sorted halves, always taking the smaller front element.
- Much faster than the
n²sorts — aboutn log nwork.
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.
Why divide-and-conquer wins
- Halving the problem each step gives the
log nfactor. - Merge sort's
n log nbeats selection/insertion sort'sn²on large arrays. - The base case (empty or one element) stops every branch.
- Same shape as all recursion: split down, combine back up.
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.
Recursive binary search recurses on ONE half (the target is only on one side); merge sort recurses on BOTH halves and then merges them. Both need a base case — an empty range means "not found" for search; a 0-or-1-element array is already sorted for merge sort. Divide-and-conquer is what makes them fast (O(log n) and O(n log n)).
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)).
Merge-sorting [3, 1, 2, 4]:
- Split into
[3, 1]and[2, 4]; sort each →[1, 3]and[2, 4]. - Merge: take 1, then 2, then 3, then 4 →
[1, 2, 3, 4]. - Each merge picks the smaller front element in turn.
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.
Recursive binary search recurses on one half (base case: empty range = not found) for O(log n) search. Merge sort recurses on both halves and merges them (base case: 0 or 1 element) for O(n log n) sorting. Both are divide-and-conquer: split down, combine back up — much faster than n².
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 · Merge sort divide em metades, depois mescla para cima
Single elements are sorted (base case); merges combine them upward. · Elementos únicos estão ordenados (caso base); mesclas os combinam para cima.
Recursive binary search recurses on... · A busca binária recursiva recursa em...
The target is only on one side of the middle. · O alvo está apenas de um lado do meio.
Merge sort recurses on... · O merge sort recursa em...
Sort each half, then merge the two sorted halves. · Ordenar cada metade, depois mesclar as duas metades ordenadas.
The base case for merge sort is an array of... · O caso base para merge sort é um array de...
One (or zero) element needs no sorting. · Um (ou zero) elemento não precisa de ordenação.
Merge sort's running time is about... · O tempo de execução do merge sort é cerca de...
log n levels of splitting, n work per level. · log n níveis de divisão, trabalho n por nível.
Both recursive binary search and merge sort are divide-and-conquer algorithms. · Tanto a busca binária recursiva quanto o merge sort são algoritmos de divide-e-conquistar.
Both split the problem in half and recurse. · Ambos dividem o problema pela metade e recursam.
Order the merge step for halves [1,3] and [2,4]. · Ordene o passo de mesclagem para as metades [1,3] e [2,4].
Always take the smaller front element: 1, 2, 3, 4. · Sempre pegar o elemento frontal menor: 1, 2, 3, 4.