Première · Numérique et sciences informatiques

Recherche dichotomique dans un tableau trié

Savoir expliquer et appliquer une recherche dichotomique pour trouver une valeur dans un tableau trié, en suivant pas à pas les indices de début, de fin et du milieu.

Aperçu gratuit
Illustration de la fiche « Recherche dichotomique dans un tableau trié »

Les points essentiels

  • La recherche dichotomique ne fonctionne que sur un tableau trié.
  • À chaque étape, on compare la valeur cherchée à la valeur de l'indice médian.

Les mots à connaître

tableau trié
Tableau dont les éléments sont rangés dans l'ordre croissant (du plus petit au plus grand).
recherche dichotomique
Méthode qui teste l’élément médian d’une zone triée, puis poursuit dans une moitié si la valeur n’est pas trouvée.

Un exemple pour comprendre

On cherche la valeur 17 dans le tableau trié [3 ; 5 ; 8 ; 12 ; 17 ; 21 ; 25]. Donne les étapes de la recherche dichotomique.

Le tableau est [3 ; 5 ; 8 ; 12 ; 17 ; 21 ; 25], de taille 7. Les indices vont de 0 à 6. Première étape : l'indice médian vaut (0 + 6) // 2 = 3, la valeur testée est 12. Comme 17 > 12, on cherche à droite de l'indice 3 : gauche devient 4. Deuxième étape : l'indice médian vaut (4 + 6) // 2 = 5, la valeur testée est 21. Comme 17 < 21, on cherche à gauche : droite devient 4. Troisième étape : l'indice médian vaut (4 + 4) // 2 = 4, la valeur testée est 17. On a trouvé 17 à l'indice 4.

Première page de l’Essentiel : Recherche dichotomique dans un tableau trié
Ketty