Recursive Searching and Sorting
Introduit| English | Sens |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | diviser pour régner |
| merge sort/mɜːdʒ sɔːt/ | tri fusion |
| merge/mɜːdʒ/ | fusion |
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.
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.
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.
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.
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)).
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.
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
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The target is only on one side of the middle.
Merge sort recurses on...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
One (or zero) element needs no sorting.
Merge sort's running time is about...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Always take the smaller front element: 1, 2, 3, 4.