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.

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.

