Au programme de ce chapitre
- I. Le principe de la dichotomie : recherche dans un tableau trié
- II. Le tri fusion
- III. Complexité du tri fusion
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition La stratégie « diviser pour régner » consiste à découper un problème en sous-problèmes plus petits de même nature, à les résoudre (souvent récursivement), puis à combiner leurs solutions. La recherche dichotomique en est l'exemple le plus simple : dans un tableau trié, on compare l'élément cherché à celui du milieu, ce qui permet d'éliminer la moitié du tableau à chaque comparaison.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3, sur un tableau trié de 12 éléments :
>>> def recherche_dichotomique(t, x):
... gauche, droite = 0, len(t) - 1
... nb_comparaisons = 0
... while gauche <= droite:
... nb_comparaisons += 1
... milieu = (gauche + droite) // 2
... if t[milieu] == x:
... return milieu, nb_comparaisons
... elif t[milieu] < x:
... gauche = milieu + 1
... else:
... droite = milieu - 1
... return -1, nb_comparaisons
...
>>> t = [3, 7, 9, 12, 18, 23, 29, 34, 41, 47, 52, 58]
>>> recherche_dichotomique(t, 34)
(7, 4)
>>> recherche_dichotomique(t, 10)
(-1, 3)Les erreurs fréquentes à éviter
Piège. N'oublie pas l'étape de COMBINAISON : diviser et résoudre ne suffisent pas, il faut fusionner les résultats.
Attention La recherche dichotomique exige un tableau trié. Sur un tableau non trié, comparer l'élément du milieu n'apporte aucune information fiable sur la position de la valeur cherchée : il faut alors se contenter d'une recherche séquentielle en O(n), ou trier le tableau au préalable.
L'astuce du prof
Astuce. Repère les trois temps : diviser → résoudre (récursion) → combiner ; applique-les au tri fusion.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Décris le principe de « diviser pour régner ».
Voir la correction
Diviser le problème en sous-problèmes, les résoudre (souvent récursivement), puis combiner les solutions.
Exercice 2
Cite un algorithme qui utilise « diviser pour régner ».
Voir la correction
Le tri fusion (merge sort) ou la recherche dichotomique.