Le problème
Soit le tableau (collection) t de longueur n contenant des valeurs entières quelconques. Le tableau est obligatoirement trié dans l’ordre croissant. On cherche à savoir si le tableau t contient une certaine valeur entière x.
Principe de l’algorithme
Pour la recherche de la valeur x, on propose la méthode de recherche par dichotomie :
- soient les deux indices gauche (indice minimum) et droite (indice maximum) du tableau tels que gauche=0 et droite= (n-1)
- soit m, le milieu de l’intervalle [gauche..droite] tel que (gauche <= m <= droite)
- si la valeur recherchée x est inférieure ou égale à t[m], alors la recherche doit se poursuivre dans l’intervalle [gauche..m], sinon dans l’intervalle [m+1..droite].
En répétant la division par 2 de l’intervalle [gauche..droite] plusieurs fois, on encadre la valeur recherchée x dans un intervalle [gauche..droite] de plus en plus petit, jusqu’à qu’il ne contienne plus qu’une valeur. A ce stade, soit t[m] est égale à la valeur recherchée x, et on l’a trouvée, sinon elle n’est pas dans le tableau.
Exemple de recherche de la valeur 42, trouvée en quatre étapes :
intervalle[0..8], m=4, 42 <= t[m]
intervalle [0..4], m=2, 42 > t[m]
intervalle [3..4], m=3, 42 <= t[m]
intervalle [3..3], 42=t[3], valeur retrouvée !
Exemple de recherche de la valeur 100, non trouvée après quatre étapes :
- intervalle[0..8], m=4, 100 > t[m]
- intervalle [5..8], m=6, 100 > t[m]
- intervalle [7..8], m=7, 100 > t[m]
- intervalle [8..8], 100 ≠ t[8], valeur non retrouvée !
Fonctionnement manuel
On positionne les indices gauche et droite. A chaque étape, on calcule le milieu m puis on compare la valeur x à t[m]. En fonction du résultat, on modifie l’indice gauche ou droite. Lorsque les deux indices sont égaux, on regarde si la valeur cherchée est à cet endroit.
Exemple en mode aveugle
Enregistrement de la boucle
- soit m, le milieu de l’intervalle [gauche..droite] tel que (gauche <= m <= droite)
- si la valeur recherchée x est inférieure ou égale à t[m], alors la recherche doit se poursuivre dans l’intervalle [gauche..m], sinon dans l’intervalle [m+1..droite].
Enregistrement complémentaire
- sinon dans l’intervalle [m+1..droite].
Sortie de la boucle
On encadre la valeur recherchée x dans un intervalle [gauche..droite] de plus en plus petit, jusqu’à qu’il ne contienne plus qu’une valeur.
Démarrage
Soient les deux indices gauche (indice minimum) et droite (indice maximum) du tableau tels que gauche=0 et droite= (n-1)
Terminaison
Cas où la valeur est trouvée
Cas non trouvé
Exécution complète
Cas d’une valeur non trouvée.
Programme AlgoTouch
const int Deux = 2 ;
int t[9] = {10, 13, 27, 42, 47, 50, 61, 77, 95} ;
index gauche of t ;
index droite of t ;
const int t.length = 9 ;
index m of t ;
int x ; // valeur recherchée
Define Dichotomie
From
gauche = 0 ;
droite = t.length ;
droite = droite – 1 ;
Read “Valeur de x” x ;
// …
Until
(gauche == droite)
// …
Loop
m = gauche + droite ;
m = m / Deux ;
if (x <= t[m]) {
droite = m ;
}
else {
// x > t[m] gauche = m ;
gauche = gauche + 1 ;
}
// …
Terminate
if (t[gauche] == x) {
Write “valeur trouvée : ” x ;
}
else {
// t[gauche] != x
Write “Non trouvée : ” x ;
}
// …
End
Programme Python
t = [10, 13, 27, 42, 47, 50, 61, 77, 95]n = len(t)
gauche = 0
droite = n – 1
v = int(input(“valeur à chercher : “))
while (gauche != droite):
m = (int) ((gauche + droite)/2)
if (v <= t[m]):
droite = m
else:
gauche = m + 1
if (v == t[gauche]):
print (“valeur trouvée”)
else:
print (“valeur non trouvée”)