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.
À chaque étape, on compare au milieu et on élimine une moitié : la zone de recherche fond très vite.
- 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 21 > 13, on garde [13] ; dernier milieu 13 → trouvé. Trois étapes 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
S'entraîner
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
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.
Qu'est-ce qu'un algorithme glouton ?
Réponse :
Un algorithme qui fait le meilleur choix local à chaque étape
Un glouton fait à chaque étape le choix qui semble le meilleur sur le moment, sans revenir en arrière.
Avec {1, 2, 5, 10, 20}, combien de pièces pour rendre 37 c (méthode gloutonne) ?
Réponse :
4
20 + 10 + 5 + 2 = 37, soit 4 pièces.
L'algorithme glouton donne-t-il toujours la solution optimale ?
Réponse :
Cela dépend du problème
Il est optimal pour certains problèmes (monnaie en euros) mais pas tous (contre-exemple {1, 3, 4}).
Avec les pièces {1, 3, 4}, quelle est la solution optimale pour rendre 6 ?
Réponse :
3+3 (2 pièces)
Le glouton donnerait 4+1+1 (3 pièces), mais l'optimal est 3+3 (2 pièces) : le glouton échoue ici.
Que renvoie la recherche dichotomique si l'élément est absent ?
Réponse :
-1 ou None
Quand la boucle se termine (gauche > droite) sans trouver, on renvoie -1 ou None pour signaler l'absence.
Combien de fois peut-on diviser 1 000 000 par 2 avant d'atteindre 1 ?
Réponse :
Environ 20
$\log_2(1\,000\,000) \approx 20$ : 20 étapes suffisent pour un million d'éléments, d'où l'efficacité de la dichotomie.