À propos de cette expérience
Recherchez la même valeur cible avec la recherche linéaire et la recherche binaire côte à côte. À chaque étape, chaque algorithme qui n’est pas terminé effectue une comparaison. La recherche binaire examine le milieu de l’intervalle trié restant ; la recherche linéaire avance d’une position à la fois. Sélectionnez une valeur cible impaire pour voir les deux algorithmes se terminer sans trouver de correspondance.
Objectifs pédagogiques
- Suivez l’intervalle des candidats et le point milieu dans la recherche binaire
- Comparez le nombre de comparaisons de la recherche linéaire et de la recherche binaire
- Expliquez pourquoi la recherche binaire nécessite des données triées et comment elle gère les valeurs cibles absentes
Comment l’utiliser
- 1Recherchez 32 dans le tableau par défaut, en effectuant une comparaison à la fois.
- 2Notez quand la recherche binaire se termine, puis continuez jusqu’à la fin de la recherche linéaire.
- 3Choisissez une valeur cible impaire, comme 31. Observez comment la recherche binaire atteint un intervalle vide.
- 4Modifiez la longueur du tableau et recherchez sa dernière valeur. Comparez les bornes dans le pire des cas.
Le modèle
Hypothèses
- Le tableau contient les entiers pairs uniques 2, 4, ..., 2n, classés par ordre croissant. L’indexation commence à zéro.
- Une comparaison de valeurs est une unique comparaison à trois issues avec la valeur cible. Les calculs d’indices et les vérifications de boucle ne sont pas comptabilisés.
- Lorsque la valeur cible est absente, la recherche linéaire parcourt tout le tableau, sans tirer parti de son ordre pour s’arrêter plus tôt.
- Chaque ligne reste dans son état terminé pendant que l’autre recherche se poursuit. L’intervalle candidat actuel est affiché avant l’application du résultat de la comparaison en cours.
À essayer en classe
- Q1Pourquoi la recherche dichotomique peut-elle éliminer la moitié des positions restantes après une seule comparaison ?
- Q2Combien de comparaisons faut-il avec chaque méthode pour trouver la dernière valeur d’un tableau de 32 valeurs ?
- Q3Qu’est-ce qui ne fonctionne pas si l’on applique la même règle du point médian à un tableau non trié ?
Foire aux questions
Pourquoi la recherche dichotomique échoue-t-elle avec une valeur cible impaire ?
Toutes les entrées du tableau sont paires. Une valeur cible impaire ne peut donc jamais correspondre à une entrée ; l’intervalle candidat finit par devenir vide et l’algorithme indique que la valeur est introuvable.
Pourquoi une ligne ne bouge-t-elle plus ?
Cette recherche est déjà terminée. L’exécution pas à pas poursuit l’autre algorithme afin de pouvoir comparer leurs coûts totaux en comparaisons.