Qu'est-ce qu'un algorithme glouton ?

Un algorithme qui fait le meilleur choix local à chaque étape

Qu'est-ce qu'un algorithme glouton ?

Un algorithme qui fait le meilleur choix local à chaque étape. Un algorithme glouton fait à chaque étape le choix qui semble le meilleur localement, sans revenir en arrière.

Pour le rendu de monnaie avec les pièces {1, 2, 5, 10, 20}, combien de pièces faut-il pour rendre 37 centimes (méthode gloutonne) ?

4. 20 + 10 + 5 + 2 = 37 centimes, soit 4 pièces.

L'algorithme glouton donne-t-il toujours la solution optimale ?

Cela dépend du problème. La stratégie gloutonne donne l'optimum pour certains problèmes (rendu de monnaie en euros) mais pas tous (contre-exemple avec les pièces {1, 3, 4}).

Avec les pièces {1, 3, 4}, quelle est la solution optimale pour rendre 6 ?

3+3 (2 pièces). L'algorithme glouton donnerait 4+1+1 (3 pièces), mais l'optimal est 3+3 (2 pièces). Le glouton n'est pas optimal ici.

Que renvoie la recherche dichotomique si l'élément n'est pas dans la liste ?

-1 ou None (non trouvé). Si la boucle se termine (gauche > droite) sans trouver l'élément, on renvoie -1 ou None pour signaler son absence.

Combien de fois peut-on diviser 1 000 000 par 2 avant d'atteindre 1 ?

Environ 20. log₂(1 000 000) ≈ 20. C'est pourquoi la recherche dichotomique est si efficace : 20 étapes suffisent pour un million d'éléments.

NSI (Spé) — Algorithmique

Recherche dichotomique et algorithmes gloutons

Q: Quelle est la précondition pour appliquer la recherche dichotomique ?

La liste doit être triée. La recherche dichotomique ne fonctionne que sur une liste triée, car elle élimine une moitié à chaque étape en se basant sur l'ordre.

Q: Quelle est la complexité de la recherche dichotomique ?

O(log n). À chaque étape, on divise la zone de recherche par 2, d'où une complexité logarithmique O(log n).

Q: Combien de comparaisons faut-il au maximum pour chercher dans une liste triée de 1024 éléments ?

11. log₂(1024) = 10, mais il faut compter la dernière comparaison, donc 11 comparaisons au maximum.

Q: Dans la recherche dichotomique, si valeur < liste[milieu], que fait-on ?

droite = milieu - 1. Si la valeur cherchée est plus petite que l'élément du milieu, elle se trouve dans la moitié gauche : on met droite = milieu - 1.

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) permet de trouver un élément dans une liste triée en O(log n) au lieu de O(n) pour la recherche séquentielle. Le principe est de diviser la zone de recherche en deux à chaque étape : on compare l'élément cherché au milieu de la liste, puis on élimine la moitié qui ne peut pas le contenir. Par exemple, dans une liste triée de 1000 éléments, il suffit d'environ 10 comparaisons (car log₂(1000) ≈ 10). Les algorithmes gloutons construisent une solution étape par étape en faisant à chaque fois le choix localement optimal, sans revenir en arrière. Le problème du rendu de monnaie est un exemple classique : on rend toujours la plus grande pièce possible. Cette stratégie ne donne pas toujours la solution optimale globale, mais elle est simple et souvent efficace.

Thème complet

Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale

Ce thème dans une autre classe

Seconde — Mathématiques

Algorithmique et programmation

Terminale — NSI (Spé)

Programmation orientée objet en Python

Terminale — NSI (Spé)

Calculabilité, décidabilité et mise au point

Articles utiles

Spécialités

Bac NSI 2026 : comment réussir l'épreuve écrite et pratique

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 pour appliquer la recherche dichotomique ?

Réponse : La liste doit être triée

La recherche dichotomique ne fonctionne que sur une liste triée, car elle élimine une moitié à chaque étape en se basant sur l'ordre.

Quelle est la complexité de la recherche dichotomique ?

Réponse : O(log n)

À chaque étape, on divise la zone de recherche par 2, d'où une complexité logarithmique O(log n).

Combien de comparaisons faut-il au maximum pour chercher dans une liste triée de 1024 éléments ?

Réponse : 11

log₂(1024) = 10, mais il faut compter la dernière comparaison, donc 11 comparaisons au maximum.

Dans la recherche dichotomique, si valeur < liste[milieu], que fait-on ?

Réponse : droite = milieu - 1

Si la valeur cherchée est plus petite que l'élément du milieu, elle se trouve dans la moitié gauche : on met droite = milieu - 1.

Résumé

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 pour appliquer la recherche dichotomique ?

Réponse : La liste doit être triée

La recherche dichotomique ne fonctionne que sur une liste triée, car elle élimine une moitié à chaque étape en se basant sur l'ordre.

Quelle est la complexité de la recherche dichotomique ?

Réponse : O(log n)

À chaque étape, on divise la zone de recherche par 2, d'où une complexité logarithmique O(log n).

Combien de comparaisons faut-il au maximum pour chercher dans une liste triée de 1024 éléments ?

Réponse : 11

log₂(1024) = 10, mais il faut compter la dernière comparaison, donc 11 comparaisons au maximum.

Dans la recherche dichotomique, si valeur < liste[milieu], que fait-on ?

Réponse : droite = milieu - 1

Si la valeur cherchée est plus petite que l'élément du milieu, elle se trouve dans la moitié gauche : on met droite = milieu - 1.

Recherche dichotomique et algorithmes gloutons

Résumé