Découvrir diviser pour régner : découper, résoudre, recombiner
Reconnaître le schéma diviser pour régner sur la recherche dichotomique et le tri fusion, en identifier les trois temps (diviser, résoudre, combiner) et justifier la terminaison par la décroissance de la taille des sous-problèmes.

Les points essentiels
- Diviser pour régner résout un problème en le découpant en sous-problèmes du même type mais de taille strictement plus petite, résolus récursivement, puis en combinant leurs résultats.
- Trois temps à identifier systématiquement : diviser (découper l'entrée), régner (appeler récursivement sur chaque morceau), combiner (assembler les résultats partiels en résultat global).
Les mots à connaître
- Diviser pour régner
- Paradigme algorithmique où l'on résout un problème de taille n en le décomposant en sous-problèmes de même nature et de taille plus petite, résolus récursivement, dont on combine les solutions.
- Cas de base
- Situation suffisamment simple pour être résolue directement, sans appel récursif (par exemple une liste de longueur 0 ou 1 pour un tri). Il arrête la récursion.
Un exemple pour comprendre
Recherche dichotomique : on cherche 23 dans la liste triée L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 à 9). Détaille les étapes et dis quels temps de diviser pour régner on reconnaît.
On prend les bornes g = 0, d = 9. Étape 1 : m = (0+9)//2 = 4, L[4] = 16 < 23, donc on garde la moitié droite : g = 5. Étape 2 : m = (5+9)//2 = 7, L[7] = 56 > 23, donc on garde la moitié gauche : d = 6. Étape 3 : m = (5+6)//2 = 5, L[5] = 23 : trouvé à l'indice 5. Seulement 3 comparaisons pour 10 éléments. Diviser : on coupe l'intervalle au milieu. Régner : on poursuit sur une seule moitié. Combiner : rien à faire, on renvoie directement le résultat. Terminaison : la largeur d - g + 1 passe de 10 à 5 puis 2 puis 1 ; elle diminue strictement à chaque étape, donc la recherche s'arrête. Si l'élément était absent, on finirait avec un intervalle vide (g > d), cas de base qui renvoie « non trouvé ».

