Recursive Searching and Sorting · Búsqueda y ordenamiento recursivos
| English | Español |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | divide y vencerás |
| merge sort/mɜːdʒ sɔːt/ | ordenamiento por fusión |
| merge/mɜːdʒ/ | se fusionarán |
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.
Recursión meets search and sort
- La misma idea de divide y vencerás (divide-and-conquer) impulsa la búsqueda binaria recursiva y el ordenamiento por fusión recursivo.
- Divide el problema a la mitad, resuelve las mitades y combínalas.
- La búsqueda binaria recursiva busca en una mitad llamándose a sí misma sobre ella.
- El ordenamiento por fusión ordena cada mitad y luego fusiona las mitades 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.
Búsqueda binaria recursiva
- Caso base: un rango vacío significa que el objetivo no se encontró.
- Mira el centro. Si es el objetivo, devuelve su índice.
- Si el objetivo es menor, recurre sobre la mitad izquierda; si es mayor, la mitad derecha.
- Cada llamada reduce el rango a la mitad — el mismo
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.
Ordenamiento por fusión
- Divide el arreglo en dos mitades; ordena cada mitad recursivamente.
- Caso base: un arreglo de 0 o 1 elemento ya está ordenado.
- Fusiona: recorre ambas mitades ordenadas, tomando siempre el elemento más pequeño del frente.
- Mucho más rápido que los ordenamientos
n²— aproximadamenten log nde trabajo.
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 qué divide y vencerás gana
- Reducir a la mitad el problema en cada paso da el factor
log n. - El
n log ndel ordenamiento por fusión supera aln²de los algoritmos de selección e inserción en arreglos grandes. - El caso base (vacío o un solo elemento) detiene cada rama.
- Mismo patrón que toda recursión: dividir hacia abajo, combinar hacia arriba.
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)).
La búsqueda binaria recursiva recurre sobre UNA mitad (el objetivo solo está en un lado); el ordenamiento por fusión recurre sobre AMBAS mitades y luego las fusiona. Ambos necesitan un caso base —un rango vacío significa "no encontrado" para la búsqueda; un arreglo de 0 o 1 elemento ya está ordenado para el ordenamiento por fusión. Es divide y vencerás lo que los hace rápidos (O(log n) y 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 por fusión [3, 1, 2, 4]:
- Dividir en
[3, 1]y[2, 4]; ordenar cada uno →[1, 3]y[2, 4]. - Fusionar: tomar 1, luego 2, luego 3, luego 4 →
[1, 2, 3, 4]. - Cada fusión selecciona el elemento más pequeño del frente en turno.
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².
La búsqueda binaria recursiva recurre sobre una mitad (caso base: rango vacío = no encontrado) para una búsqueda O(log n). El ordenamiento por fusión recurre sobre ambas mitades y las fusiona (caso base: 0 o 1 elemento) para un ordenamiento O(n log n). Ambos son divide y vencerás: dividen hacia abajo, combinan hacia arriba — mucho más rápidos que n².
Merge sort splits into halves, then merges up · La ordenación por fusión se divide en mitades, luego se fusiona hacia arriba
Single elements are sorted (base case); merges combine them upward. · Los elementos individuales están ordenados (caso base); las fusiones los combinan hacia arriba.
Recursive binary search recurses on... · La búsqueda binaria recursiva recursiona sobre...
The target is only on one side of the middle. · El objetivo solo está en un lado del medio.
Merge sort recurses on... · La ordenación por fusión recursiona sobre...
Sort each half, then merge the two sorted halves. · Ordenar cada mitad, luego fusionar las dos mitades ordenadas.
The base case for merge sort is an array of... · El caso base para la ordenación por fusión es un arreglo de...
One (or zero) element needs no sorting. · Un (o cero) elemento no necesita ordenamiento.
Merge sort's running time is about... · El tiempo de ejecución de la ordenación por fusión es aproximadamente...
log n levels of splitting, n work per level. · log n niveles de división, trabajo n por nivel.
Both recursive binary search and merge sort are divide-and-conquer algorithms. · Tanto la búsqueda binaria recursiva como la ordenación por fusión son algoritmos de dividir para vencer.
Both split the problem in half and recurse. · Ambos dividen el problema a la mitad y recursionan.
Order the merge step for halves [1,3] and [2,4]. · Ordena el paso de fusión para las mitades [1,3] y [2,4].
Always take the smaller front element: 1, 2, 3, 4. · Siempre tomar el elemento frontal más pequeño: 1, 2, 3, 4.