Recherche dichotomique et diviser pour régner
Cette fiche résume la recherche dichotomique et la stratégie diviser pour régner, avec correction et complexité.
1
Principe général
Idée clé
Diviser pour régner consiste à découper un problème, résoudre les sous-problèmes, puis combiner.
- Le problème est transformé en sous-problèmes plus petits.
- Les sous-problèmes doivent rester du même type.
- On s'arrête sur un cas de base simple.
Mémo
Pense à DRC : Diviser, Résoudre, Combiner.
2
Correction et arrêt
Invariant et terminaison
- 1
L'élément recherché reste dans l'intervalle courant.
- 2
On compare avec l'élément du milieu.
Cas de base
| Situation | Conclusion |
|---|---|
| Intervalle vide | L'élément est absent. |
| Un seul élément | On conclut par comparaison finale. |
3
Découpages classiques
Schéma fréquent
Exemples à reconnaître
- La recherche dichotomique coupe un intervalle en deux.
- Le découpage en moitiés de taille proche est typique.
- Cette fiche résume la recherche dichotomique et la stratégie diviser pour régner, avec correction et complexité.