NSI (Spé) — Algorithmique
Recherche dichotomique et algorithmes gloutons
Recherche efficace dans une liste triée, stratégie gloutonne
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
La **recherche dichotomique** (ou binaire) trouve un élément dans une liste **triée** en $O(\log n)$, au lieu de $O(n)$ pour la recherche séquentielle. Le principe : **diviser par deux** la zone de recherche à chaque étape, en comparant la valeur cherchée à l'élément du **milieu** puis en éliminant la moitié impossible. Dans une liste triée de 1000 éléments, une dizaine de comparaisons suffisent (car $\log_2(1000) \approx 10$). Les **algorithmes gloutons** construisent une solution étape par étape en faisant à chaque fois le **choix localement optimal**, sans revenir en arrière. Le **rendu de monnaie** en est l'exemple type : on rend toujours la plus grande pièce possible. Cette stratégie ne donne pas toujours l'optimum global, mais elle est simple et souvent efficace.
Chercher un élément dans une liste **triée** ne demande pas de tout parcourir. La **dichotomie** compare la valeur au **milieu** et, selon le résultat, élimine d'un coup **la moitié** des candidats. En quelques étapes seulement, on tranche, même sur des millions d'éléments.
- **Précondition :** la liste doit être **triée** pour appliquer la dichotomie.
- **Principe :** comparer la valeur au milieu, éliminer la moitié impossible, recommencer.
- **Variables :** gauche = 0, droite = len(liste)-1, milieu = (gauche + droite) // 2.
- **Décision :** valeur < liste[milieu] → chercher à gauche ; sinon à droite.
- **Complexité :** $O(\log_2 n)$, bien plus rapide que la recherche séquentielle $O(n)$.
Exemple
Chercher 13 dans [2, 5, 8, 11, 13, 21, 34, 40] : le milieu est 11 < 13, on garde la moitié droite [13, 21, 34, 40] ; nouveau milieu 13 → trouvé. Deux comparaisons suffisent.
Piège à éviter
Oublier la condition d'arrêt **gauche <= droite** mène à une boucle infinie ou à un dépassement d'indice. Et la dichotomie ne fonctionne **que** sur une liste triée : sur une liste quelconque, son résultat n'a aucun sens.
Traduisons le principe en code. La version **itérative** maintient deux bornes gauche et droite qui se rapprochent jusqu'à encadrer (ou non) la valeur. À chaque tour, on recalcule le milieu et on déplace l'une des bornes.
- **Boucle :** while gauche <= droite: milieu = (gauche + droite) // 2.
- **Trouvé :** if liste[milieu] == valeur: return milieu (l'indice).
- **Trop grand :** if valeur < liste[milieu]: droite = milieu - 1 (moitié gauche).
- **Trop petit :** if valeur > liste[milieu]: gauche = milieu + 1 (moitié droite).
- **Absent :** si la boucle se termine sans trouver, return -1 ou None.
Exemple
def dicho(liste, valeur):\n g, d = 0, len(liste) - 1\n while g <= d:\n m = (g + d) // 2\n if liste[m] == valeur: return m\n if valeur < liste[m]: d = m - 1\n else: g = m + 1\n return -1
Piège à éviter
Bien mettre droite = milieu - 1 (et non milieu) : laisser droite = milieu sans réduire l'intervalle empêche la boucle de finir. Le milieu vient d'être testé, on l'**exclut** du nouvel intervalle.
Un algorithme **glouton** construit sa solution pas à pas en saisissant à chaque étape le **meilleur choix immédiat**, sans jamais se raviser. C'est simple et souvent rapide, mais ce choix local optimal ne mène pas toujours à la **meilleure solution globale**.
- **Stratégie :** à chaque étape, faire le choix **localement optimal**.
- **Pas de retour :** une fois un choix fait, on ne le remet pas en question.
- **Avantages :** simple à coder, souvent rapide.
- **Limite :** ne garantit pas toujours l'optimum **global**.
- **Cas favorable :** sur certains problèmes (rendu de monnaie en euros), le glouton donne l'optimum.
Exemple
Pour traverser une rivière sur des pierres en minimisant les sauts, un glouton choisit à chaque fois la pierre la plus lointaine atteignable. Simple, mais selon le problème, cette avidité peut rater la meilleure trajectoire.
Piège à éviter
« Localement optimal » ne veut pas dire « globalement optimal » : le glouton peut s'enfermer dans une impasse. Il faut **prouver** qu'il donne l'optimum pour un problème donné avant de s'y fier.
Le **rendu de monnaie** illustre parfaitement le glouton : rendre une somme avec le **moins de pièces possible**. La stratégie gloutonne rend toujours la **plus grande pièce** qui ne dépasse pas. Elle est optimale pour le système euro, mais un contre-exemple montre ses limites.
- **Problème :** rendre une somme avec le minimum de pièces ou de billets.
- **Stratégie :** toujours choisir la plus grande pièce qui ne dépasse pas la somme restante.
- **Exemple euro :** rendre 47 c avec {20, 10, 5, 2, 1} → 20 + 20 + 5 + 2, soit 4 pièces.
- **Système euro :** le glouton donne **toujours** l'optimum.
- **Autres usages gloutons :** sac à dos fractionnaire, ordonnancement de tâches.
Exemple
Rendre 6 avec les pièces {1, 3, 4}. Glouton : prendre 4, puis 1 et 1 → 3 pièces. Optimal : 3 + 3 → 2 pièces. Ici le glouton **échoue** à trouver le minimum.
Piège à éviter
Avec un système de pièces quelconque, le glouton n'est **pas** garanti optimal (contre-exemple {1, 3, 4} pour 6). Pour garantir le minimum sur n'importe quel système, il faut la programmation dynamique.
Quiz - Recherche dichotomique et algorithmes gloutons
10 questions
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Questions fréquentes
Les points clés à retenir sur Recherche dichotomique et algorithmes gloutons, extraits du quiz de révision.
Quelle est la précondition de la recherche dichotomique ?
Réponse :
La liste doit être triée
La dichotomie ne marche que sur une liste **triée**, car elle élimine une moitié en s'appuyant sur l'ordre.
Quelle est la complexité de la recherche dichotomique ?
Réponse :
$O(\log n)$
On divise la zone de recherche par 2 à chaque étape, d'où une complexité logarithmique $O(\log n)$.
Combien de comparaisons au maximum pour chercher dans une liste triée de 1024 éléments ?
Réponse :
11
$\log_2(1024) = 10$ divisions, mais il faut une comparaison de plus pour conclure : 11 au maximum.
Dans la dichotomie, si valeur < liste[milieu], que fait-on ?
Réponse :
droite = milieu - 1
La valeur est plus petite que le milieu : elle est dans la moitié gauche, donc droite = milieu - 1.