Recherche séquentielle et recherche dichotomique – compter les comparaisons

Ce qu’elle montre

La recherche séquentielle examine les éléments un par un depuis le début : dans le pire des cas, elle fait autant de comparaisons qu’il y a d’éléments. La recherche dichotomique compare la valeur cherchée à l’élément du milieu d’un tableau trié et écarte la moitié qui ne peut pas la contenir ; elle fait donc au plus environ log₂n + 1 comparaisons, cinq seulement pour seize éléments. Compter les comparaisons des deux algorithmes sur le même tableau montre pourquoi la dichotomie l’emporte sur les longues listes, et pourquoi elle exige des données triées.

Mode d’emploi

Réglez Algorithme sur Les deux (comparer), choisissez le Nombre d’éléments et cliquez sur Pas à pas pour suivre chaque comparaison : la case surlignée, les repères low, mid et high et la partie du tableau écartée. Cliquez sur une case pour changer la valeur cherchée, ou utilisez Lecture pour une exécution complète. Essayez une valeur proche du début du tableau, puis décochez Tableau trié par ordre croissant pour voir pourquoi la dichotomie ne fonctionne plus.

Paramètres modifiables

• Nombre d’éléments 5–20
• Valeur cherchée (0 = tirée au hasard dans le tableau) 0–99
• Algorithme Les deux (comparer), Recherche séquentielle, Recherche dichotomique
• Tableau trié par ordre croissant
• Vitesse d’exécution 1–5 étapes/s

Questions à explorer

1. Combien de comparaisons la recherche dichotomique fait-elle au maximum pour trouver une valeur dans un tableau de 16 éléments ?
2. Pour quelles valeurs cherchées la recherche séquentielle fait-elle moins de comparaisons que la dichotomie ?
3. Pourquoi la recherche dichotomique ne peut-elle plus être utilisée quand le tableau n’est pas trié ?