Recursive Searching and Sorting · Recherche et tri récursifs
| English | Français |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | diviser pour régner |
| merge sort/mɜːdʒ sɔːt/ | tri fusion |
| merge/mɜːdʒ/ | se fusionner |
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.
Récursivité et recherche/tri
- La même idée de division et conquête 分治 alimente la recherche binaire récursive et le tri fusion 归并排序.
- Divisez le problème en deux, résolvez les moitiés, combinez.
- La recherche binaire récursive cherche dans une moitié en s'appelant elle-même dessus.
- Le trier par fusion trie chaque moitié, puis fusionne les deux moitiés triées ensemble.
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.
Recherche binaire récursive
- Cas de base : une plage vide signifie que la cible n'est pas trouvée.
- Regardez le milieu. Si c'est la cible, retournez son indice.
- Si la cible est plus petite, récursez sur la moitié gauche ; si plus grande, sur la moitié droite.
- Chaque appel divise la plage par deux — le même
O(log n), écrit récursivement.
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.
Trier par fusion
- Découpez le tableau en deux moitiés ; triez chaque moitié récursivement.
- Cas de base : un tableau de 0 ou 1 élément est déjà trié.
- Fusionner 合并 : parcourir les deux moitiés triées, toujours prendre l'élément frontal le plus petit.
- Bien plus rapide que les tries
n²— environn log nde travail.
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.
Pourquoi la division et conquête gagnent
- Diviser le problème par deux à chaque étape donne le facteur
log n. - Le tri fusion
n log nbat le tri par sélection/tri par insertionn²sur les grands tableaux. - Le cas de base (vide ou un seul élément) arrête toutes les branches.
- Même forme que toute récursion : diviser vers le bas, combiner vers le haut.
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 recherche binaire récursive récurse sur UNE seule moitié (la cible n'est que d'un côté) ; le tri par fusion récurse sur LES DEUX moitiés puis les fusionne. Tous deux ont besoin d'un cas de base : une plage vide signifie « non trouvé » pour la recherche ; un tableau de 0 ou 1 élément est déjà trié pour le tri par fusion. C'est la division et conquête qui les rend rapides (O(log n) et 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.
Tri par fusion [3, 1, 2, 4] :
- Divisez en
[3, 1]et[2, 4]; triez chacun →[1, 3]et[2, 4]. - Fusionner : prendre 1, puis 2, puis 3, puis 4 →
[1, 2, 3, 4]. - Chaque fusion choisit l'élément frontal le plus petit à tour de rôle.
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 recherche binaire récursive récurse sur une seule moitié (cas de base : plage vide = non trouvé) pour la recherche O(log n). Le tri par fusion récurse sur les deux moitiés et les fusionne (cas de base : 0 ou 1 élément) pour le tri O(n log n). Tous deux sont division et conquête : diviser vers le bas, combiner vers le haut — bien plus rapide que n².
Merge sort splits into halves, then merges up · Le tri fusion divise en moitiés, puis fusionne vers le haut
Single elements are sorted (base case); merges combine them upward. · Les éléments uniques sont triés (cas de base) ; les fusions les combinent vers le haut.
Recursive binary search recurses on... · La recherche binaire récursive récurse sur...
The target is only on one side of the middle. · La cible n'est que d'un seul côté du milieu.
Merge sort recurses on... · Le tri fusion récursive récurse sur...
Sort each half, then merge the two sorted halves. · Triez chaque moitié, puis fusionnez les deux moitiés triées.
The base case for merge sort is an array of... · Le cas de base pour le tri fusion est un tableau de...
One (or zero) element needs no sorting. · Un (ou zéro) élément ne nécessite aucun tri.
Merge sort's running time is about... · Le temps d'exécution du tri fusion est d'environ...
log n levels of splitting, n work per level. · log n niveaux de division, travail n par niveau.
Both recursive binary search and merge sort are divide-and-conquer algorithms. · À la fois la recherche binaire récursive et le tri fusion sont des algorithmes de type diviser pour régner.
Both split the problem in half and recurse. · Les deux divisent le problème en deux et récursent.
Order the merge step for halves [1,3] and [2,4]. · Ordonnez l'étape de fusion pour les moitiés [1,3] et [2,4].
Always take the smaller front element: 1, 2, 3, 4. · Prendre toujours le plus petit élément frontal : 1, 2, 3, 4.