Dichotomie et algorithmes gloutons

La recherche dichotomique exige un tableau trié selon l’ordre utilisé pour comparer les valeurs. On maintient une zone possible, délimitée ici par deux indices inclusifs g et d. Au départ, g vaut 0 et d vaut n − 1. Si g ≤ d, on choisit le milieu entier m = (g + d) // 2. On compare la valeur t[m] à la cible x. Une égalité termine la recherche ; sinon, l’ordre permet d’éliminer le milieu et tout un côté.

Si t[m] < x, toutes les valeurs situées avant ou au milieu sont trop petites : on affecte m + 1 à g. Si t[m] > x, les valeurs au milieu et après sont trop grandes : on affecte m − 1 à d. Les deux décalages excluent la case déjà examinée. On poursuit tant que la zone n’est pas vide. Si g dépasse d sans égalité, on conclut à l’absence. Dans notre convention, une recherche d’indice renvoie −1 pour cette absence.

Le tableau vide se traite naturellement : n = 0 donne g = 0 et d = −1, donc la boucle ne démarre pas. Avec des valeurs répétées, cette version peut renvoyer n’importe quelle occurrence rencontrée ; elle ne garantit pas la première. La demande doit le préciser. Si le tableau n’est pas trié, les éliminations ne sont plus justifiées. Un résultat correct obtenu par hasard sur une entrée désordonnée ne valide pas l’algorithme dans ce cas.

L’invariant peut s’énoncer ainsi : si la cible est présente et n’a pas été trouvée, au moins une de ses occurrences appartient à la zone de g à d. Au départ, cette zone couvre tout le tableau. Lors d’une comparaison, le tri justifie que la partie éliminée ne contient pas la cible. L’invariant est donc conservé. Si la zone devient vide, il ne reste aucune occurrence possible ; si une égalité est trouvée, l’indice renvoyé désigne effectivement la cible.

Un variant est une quantité entière non négative qui diminue strictement lorsque la boucle continue. Ici, le nombre de cases de la zone, d − g + 1, convient tant que la zone est non vide. Après une comparaison sans égalité, le milieu est exclu et la zone restante est strictement plus petite. La boucle ne peut donc pas continuer indéfiniment. L’invariant explique la validité du résultat ; le variant explique l’arrêt. Ces deux arguments répondent à des questions différentes.

La taille de la zone est divisée approximativement par deux à chaque étape. Pour n ≥ 1, au plus floor(log₂ n) + 1 valeurs médianes sont examinées dans cette version. Le coût en examens est logarithmique, contrairement au parcours linéaire. Ce compte ne désigne pas toutes les opérations élémentaires du code : une étape peut contenir un test d’égalité puis une comparaison d’ordre. Si les données doivent d’abord être triées, le coût de ce tri doit aussi être pris en compte.

Un algorithme glouton construit progressivement une solution en choisissant à chaque étape ce qui paraît le plus avantageux selon une règle fixée. Il ne revient pas sur les choix déjà effectués. Pour rendre de la monnaie, une règle possible est de prendre la plus grande pièce qui ne dépasse pas la somme restante. Il faut disposer des valeurs de pièces, connaître leur disponibilité et annoncer l’objectif, par exemple minimiser le nombre de pièces. Obtenir la bonne somme ne prouve pas encore que le nombre de pièces est minimal.

Pour le système de pièces 10, 5, 2 et 1, rendre 18 par cette règle donne 10, puis 5, puis 2 et enfin 1. La somme restante décroît de 18 à 8, 3, 1 puis 0. La présence de la pièce 1 et une réserve suffisante permettent d’atteindre toute somme entière positive dans ce modèle. Sans pièce adaptée à un reste, le procédé peut se bloquer. La terminaison et la réussite dépendent donc de conditions explicites, pas du seul nom « glouton ».

Le problème du sac à dos demande de choisir des objets sous une contrainte de capacité. Dans sa version entière, un objet est choisi en entier ou pas du tout, et chaque objet n’est disponible qu’une fois. Une règle gloutonne peut choisir le meilleur rapport valeur sur masse. Elle peut pourtant échouer : avec une capacité 10, un objet A de masse 6 et de valeur 12 a un rapport 2 ; deux objets B et C de masse 5 et de valeur 9 ont chacun un rapport 1,8. Choisir A laisse une capacité 4 et une valeur 12, tandis que B et C donnent ensemble 18.

Ce contre-exemple concerne des objets indivisibles. Autoriser des fractions d’objets change le problème et peut changer les garanties d’une stratégie. Avant de comparer des solutions, vérifie qu’elles respectent les mêmes contraintes : capacité, disponibilité et divisibilité. Une solution irréalisable n’est pas un meilleur optimum. Pour établir qu’un glouton est optimal dans un problème donné, il faut un argument général ; quelques essais favorables montrent seulement qu’il a réussi sur ces entrées.

Retrouve S’entraîner à l’adresse /exercices. Compare une recherche présente et une recherche absente, puis essaie de réfuter une stratégie gloutonne sur un petit cas vérifiable.