Quelle est la différence entre recherche dichotomique et algorithme glouton ?

La recherche dichotomique sert à trouver un élément dans un tableau trié en divisant l'espace de recherche par deux à chaque étape. Un algorithme glouton résout des problèmes d'optimisation en faisant le meilleur choix local à chaque étape, sans garantie d'optimalité globale.

La recherche dichotomique est-elle toujours plus rapide qu'une recherche linéaire ?

Oui, sur un tableau trié, la recherche dichotomique a une complexité logarithmique O(log n) alors que la recherche linéaire est linéaire O(n). Pour 1 million d'éléments, la dichotomie nécessite au plus 20 comparaisons, contre 1 million pour la linéaire.

Peut-on utiliser un algorithme glouton pour la recherche dichotomique ?

Non, ce sont des paradigmes différents. La recherche dichotomique est un algorithme de recherche précis, tandis que les algorithmes gloutons sont utilisés pour l'optimisation. Les confondre est une erreur fréquente en NSI.

Quels sont les exemples classiques d'algorithmes gloutons au programme NSI ?

Les exemples typiques sont : le rendu de monnaie (avec pièces canoniques), le problème du sac à dos fractionnaire, l'ordonnancement de tâches (choisir la tâche qui finit le plus tôt), et l'algorithme de Dijkstra pour les plus courts chemins.

Comment prouver qu'un algorithme glouton est optimal ?

On utilise souvent un argument d'échange ou une preuve par induction. Il faut montrer que la solution gloutonne est au moins aussi bonne que n'importe quelle autre solution, en transformant une solution optimale en solution gloutonne sans perdre en qualité.

Recherche dichotomique vs algorithmes gloutons : ne plus confondre en NSI

En NSI, tu vas croiser deux types d’algorithmes qui portent des noms un peu barbares : la recherche dichotomique (ou recherche binaire) et les algorithmes gloutons. À première vue, ils n’ont rien à voir, mais beaucoup d’élèves les confondent parce qu’ils sont souvent abordés dans le même chapitre sur l’efficacité. Pas de panique : on va clarifier tout ça avec des exemples concrets, du code Python, et des astuces pour le bac.

Qu’est-ce qu’un algorithme ? Petit rappel

Un algorithme, c’est une suite d’instructions qui résout un problème. En NSI, tu apprends à en concevoir, à les analyser (complexité) et à les comparer. La recherche dichotomique et les algorithmes gloutons sont deux paradigmes différents : le premier sert à chercher rapidement dans une structure ordonnée, le second à résoudre des problèmes d’optimisation en faisant des choix locaux.

La recherche dichotomique : l’art de diviser pour régner

La recherche dichotomique (ou recherche binaire) est un algorithme qui permet de trouver la position d’un élément dans un tableau trié. Son principe : comparer l’élément cherché avec l’élément au milieu du tableau, puis éliminer la moitié de la recherche à chaque étape. C’est ultra rapide : complexité en O(log n).

Fonctionnement pas à pas

Imagine une liste triée de nombres : [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]. Tu cherches 23.

Étape 1 : prends l’indice du milieu (ici 4, valeur 16). 23 > 16, donc cherche à droite.
Étape 2 : nouveau milieu (indice 7, valeur 45). 23 < 45, cherche à gauche.
Étape 3 : milieu (indice 5, valeur 23). Trouvé !

En 3 étapes, c’est plié. Avec une recherche linéaire, il en aurait fallu 6.

Code Python de la recherche dichotomique

def recherche_dichotomique(liste, cible):
    gauche, droite = 0, len(liste) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == cible:
            return milieu
        elif liste[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

# Exemple
tableau = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
print(recherche_dichotomique(tableau, 23))  # Affiche 5

Ce code est un classique du bac NSI. Il faut absolument le connaître par cœur et comprendre pourquoi il fonctionne.

Quand utiliser la recherche dichotomique ?

Dès que tu as une structure triée (liste, dictionnaire, etc.) et que tu veux un accès rapide. Par exemple, dans un dictionnaire de mots, pour vérifier si un mot existe. En revanche, si la donnée n’est pas triée, il faut d’abord trier, ce qui peut coûter cher.

Les algorithmes gloutons : faire le meilleur choix local

Un algorithme glouton (greedy algorithm) résout un problème d’optimisation en prenant à chaque étape la décision qui semble la meilleure sur le moment, sans se soucier des conséquences futures. Il espère qu’une série de choix locaux optimaux mènera à une solution globale optimale. Ce n’est pas toujours le cas, mais pour certains problèmes, ça marche.

Exemple : le rendu de monnaie glouton

Tu dois rendre une somme avec le moins de pièces possible, avec des pièces de 1, 2, 5, 10, 20, 50 centimes. L’algorithme glouton prend la plus grande pièce possible à chaque fois. Pour 63 centimes : 50 + 10 + 2 + 1 = 4 pièces. C’est optimal ici, mais pas avec d’autres systèmes de pièces (par exemple 1, 3, 4 : pour 6, le glouton donne 4+1+1, alors que 3+3 est mieux).

Code Python d’un algorithme glouton pour le rendu de monnaie

def rendu_glouton(somme, pieces):
    pieces.sort(reverse=True)
    resultat = []
    for piece in pieces:
        while somme >= piece:
            resultat.append(piece)
            somme -= piece
    return resultat

pieces = [1, 2, 5, 10, 20, 50]
print(rendu_glouton(63, pieces))  # [50, 10, 2, 1]

Un autre exemple classique : le problème du sac à dos fractionnaire

Tu as un sac de capacité 50 kg, et des objets avec un poids et une valeur. Tu peux prendre des fractions d’objet. L’algorithme glouton prend les objets avec le meilleur rapport valeur/poids en premier. C’est optimal pour la version fractionnaire.

Les différences fondamentales

Voici un tableau récapitulatif pour ne plus jamais confondre :

Objectif : Dichotomie : chercher un élément. Glouton : optimiser (maximiser/minimiser).
Principe : Dichotomie : diviser par deux. Glouton : choix local optimal.
Données : Dichotomie : tableau trié. Glouton : souvent non trié, mais on peut trier.
Complexité : Dichotomie : O(log n). Glouton : souvent O(n log n) ou O(n).
Optimalité : Dichotomie : toujours exact. Glouton : pas toujours globalement optimal.

Cas d’usage concrets en NSI

En classe de Première NSI, tu vois la recherche dichotomique dans le thème « Algorithmique » et les algorithmes gloutons en Terminale dans « Algorithmique avancée ». Au bac, on te demandera souvent d’expliquer un algorithme, de le coder ou de le comparer. Par exemple : « Explique pourquoi la recherche dichotomique est plus efficace qu’une recherche linéaire sur une liste triée de 10 000 éléments. » Ou « Propose un algorithme glouton pour le problème du voyageur de commerce (version simplifiée). »

Pour t’entraîner, consulte les exercices NSI sur notre site, ou révise avec les fiches de révision. Tu peux aussi approfondir avec les cours complets sur https://www.nsi-lycee.fr/cours.

Comment les distinguer facilement ?

Quand tu lis un énoncé, pose-toi ces questions :

Est-ce qu’on cherche un élément dans une structure ? → Dichotomie.
Est-ce qu’on veut une solution optimale (minimum de pièces, maximum de valeur) avec des choix séquentiels ? → Glouton.
Est-ce que la donnée doit être triée pour que l’algorithme fonctionne ? → Dichotomie (sinon, il faut trier d’abord).

Un piège courant : on te demande d’écrire un algorithme « efficace » pour chercher dans une liste triée. Si tu réponds « algorithme glouton », c’est faux. La bonne réponse est « recherche dichotomique ».

Pour aller plus loin : liens utiles

Si tu veux réviser avec d’autres ressources, jette un œil sur AlloBac et AlloLycée qui proposent des fiches et des vidéos sur ces notions.

Conclusion

Maintenant, tu sais faire la différence entre la recherche dichotomique et les algorithmes gloutons. La dichotomie, c’est pour chercher vite dans du trié ; le glouton, c’est pour optimiser pas à pas. Entraîne-toi avec des exemples, code-les en Python, et tu seras prêt pour le bac. Et souviens-toi : en NSI, la pratique est la clé. Alors, à ton éditeur !