Tracer une recherche binaire

Tracer une recherche binaire

La recherche binaire sert à trouver une valeur cible dans une liste triée en réduisant progressivement la partie à examiner. Un tracé demande de montrer, étape par étape, comment l’intervalle de recherche change et ce qu’il se passe au milieu.

Méthode à suivre

1. Vérifie que la liste est triée. La recherche binaire n’est correcte que sur des données ordonnées.
2. Fixe les bornes de départ. Commence avec la première et la dernière position de la partie encore cherchée.
3. Repère l’élément du milieu. Compare la cible à la valeur centrale.
4. Choisis le nouvel intervalle.
   • Si la cible est plus petite, garde la moitié gauche.
   • Si la cible est plus grande, garde la moitié droite.
   • Si elles sont égales, on s’arrête.
5. Répète jusqu’à trouver la cible ou jusqu’à ce que l’intervalle soit vide.

Comment simplifier la réponse finale

La réponse finale doit généralement être l’issue du tracé écrite clairement : position trouvée, nombre d’étapes, ou dernier intervalle/état après la dernière comparaison. En cas de valeurs répétées ou de cas limites, conserve exactement le résultat obtenu par le déroulement de la recherche.

Vérification rapide

Assure-toi que chaque étape découle bien de la précédente et que l’intervalle diminue à chaque fois. Si la cible est trouvée, la valeur centrale finale doit être égale à la cible ; sinon, la recherche doit se terminer sans intervalle valide.