Recherche dichotomique dans un tableau trié

Introduction

Dans la leçon précédente, nous avons répondu à une question cruciale : pourquoi la recherche dichotomique exige-t-elle un tableau trié ? Vous avez compris que c'est cette condition qui nous permet d'exploiter une stratégie de "diviser pour régner", en éliminant la moitié de l'espace de recherche à chaque étape.

Aujourd'hui, nous allons nous concentrer sur le comment. L'objectif est de formaliser cette logique et de l'implémenter sous forme d'algorithme. Vous apprendrez à manipuler les variables et les structures de contrôle pour traduire cette idée puissante en instructions concrètes. À la fin de cette leçon, vous serez capable d'écrire l'algorithme de recherche dichotomique en pseudo-code.

1. La mécanique de la recherche dichotomique

Pour implémenter la recherche dichotomique, nous avons besoin de suivre l'évolution de notre "zone de recherche" à l'intérieur du tableau. Pour cela, nous utilisons trois variables principales :

• gauche (ou debut) : un "pointeur" qui marque l'indice du début de la zone de recherche. Au départ, c'est 0.
• droite (ou fin) : un pointeur qui marque l'indice de la fin de la zone de recherche. Au départ, c'est l'indice du dernier élément du tableau.
• milieu : l'indice de l'élément central de la zone de recherche actuelle.

L'algorithme se déroule dans une boucle. À chaque tour de boucle, on effectue les actions suivantes :

1. On calcule l'indice du milieu : milieu = (gauche + droite) // 2. On utilise la division entière // pour s'assurer d'obtenir un indice valide.
2. On compare l'élément à la position milieu avec la valeur que l'on cherche.
3. Selon le résultat, on ajuste les pointeurs gauche ou droite pour réduire la zone de recherche.

La recherche s'arrête dans deux cas :

• Succès : On a trouvé l'élément.
• Échec : Le pointeur gauche devient plus grand que le pointeur droite (gauche > droite). Cela signifie que la zone de recherche est devenue vide, et donc que l'élément n'est pas dans le tableau.

2. Trace manuelle : suivre les variables

Rien de tel qu'une trace manuelle pour bien comprendre le mécanisme. La ressource suivante détaille un exemple pas à pas. Reprenons l'exemple de la recherche de la valeur 40 que nous avions vu, mais cette fois-ci, portez une attention particulière à la mise à jour des variables g, d et c.

Pour visualiser l'ensemble du processus en un coup d'œil, l'image ci-dessous retrace la recherche de la valeur 35 dans un autre tableau.

3. Formalisation en pseudo-code

Maintenant que nous avons une vision claire du déroulement, nous pouvons le structurer en un algorithme formel. Le pseudo-code permet de décrire la logique sans se soucier de la syntaxe d'un langage de programmation spécifique.

La ressource suivante présente l'algorithme de recherche dichotomique en pseudo-code.

Analysons ensemble ce pseudo-code :

FONCTION recherche_dicho(t, x)
    // Entrées : t (tableau trié), x (élément cherché)
    // Sortie : indice de x dans t, ou -1 si non trouvé

    r ← -1        // 'r' pour résultat. Initialisé à -1 (non trouvé)
    g ← 0         // 'g' pour gauche. Pointeur de début.
    d ← longueur(t) - 1 // 'd' pour droite. Pointeur de fin.

    // La boucle continue tant que la zone de recherche est valide (g <= d)
    // ET que l'élément n'a pas été trouvé (r == -1).
    TANT QUE (g <= d) ET (r == -1)
        c ← (g + d) // 2 // 'c' pour centre. Calcul du milieu.

        SI t[c] < x
            // L'élément cherché est dans la moitié droite
            g ← c + 1
        SINON SI t[c] > x
            // L'élément cherché est dans la moitié gauche
            d ← c - 1
        SINON
            // t[c] == x : On a trouvé l'élément !
            r ← c // On stocke l'indice et on sortira de la boucle.
        FIN SI
    FIN TANT QUE

    RETOURNER r // Retourne l'indice trouvé, ou -1 si la boucle s'est terminée sans trouver x.

Ce pseudo-code est le cœur de ce que vous devez retenir. Il est la traduction directe de la logique que nous avons explorée.

Pour voir à quoi cela pourrait ressembler dans un langage de programmation réel, vous pouvez consulter la version itérative en Python dans la ressource suivante.

4. À vous de jouer !

La meilleure façon d'assimiler un algorithme est de l'exécuter soi-même. Prenez un papier et un crayon.

Exercice :
Soit le tableau trié suivant : T = [11, 23, 25, 38, 42, 57, 61, 74, 80, 89, 95].
Tracez l'exécution de l'algorithme de recherche dichotomique pour trouver la valeur 80.

Pour chaque tour de boucle, notez les valeurs de g, d, et c, ainsi que la comparaison effectuée.

Conclusion

Félicitations ! Vous avez franchi une étape majeure aujourd'hui. Non seulement vous comprenez la logique de la recherche dichotomique, mais vous êtes maintenant capable de la formaliser et de la tracer.

Points clés à retenir :

• L'algorithme de recherche dichotomique s'implémente à l'aide de trois pointeurs d'indice : gauche, droite, et milieu.
• Une boucle TANT QUE gère le processus de recherche, qui continue tant que la zone de recherche (gauche <= droite) est valide.
• À chaque itération, la zone de recherche est divisée par deux en mettant à jour soit le pointeur gauche, soit le pointeur droite, en fonction de la comparaison avec l'élément central.
• L'algorithme se termine soit par la découverte de l'élément, soit lorsque la zone de recherche devient vide, indiquant que l'élément est absent.

Et après ?

Nous avons maintenant étudié deux algorithmes de recherche : la recherche linéaire (simple mais potentiellement lente) et la recherche dichotomique (très rapide mais nécessitant un tableau trié). Cette dernière nous amène naturellement à un autre sujet fondamental de l'algorithmique : le tri.

Dans la prochaine leçon, nous allons commencer à explorer les algorithmes de tri. Nous débuterons avec l'un des plus intuitifs : le tri par sélection. Vous découvrirez comment organiser un tableau en désordre pour pouvoir, par la suite, y effectuer des recherches efficaces.