Cette page suit toujours le même plan : le principe en une phrase, les étapes dans l'ordre exact, une démonstration interactive, le code Python, puis le nombre de comparaisons et la complexité.
Utilisation de la démonstration
La démonstration avance uniquement quand vous cliquez sur « Suivant » ou « Précédent » : rien ne bouge tout seul. Un bouton « Lecture automatique » est disponible si vous préférez laisser les étapes défiler seules, à une vitesse que vous choisissez.
1. Vocabulaire à connaître avant de commencer
Chaque mot ci-dessous est utilisé exactement dans ce sens dans toute la page.
Mot
Définition précise
Tableau trié
Un tableau dont les valeurs sont rangées par ordre croissant. La recherche dichotomique ne fonctionne que sur un tableau trié.
Indice
Le numéro qui repère une case du tableau. Le premier indice est 0, pas 1.
Intervalle de recherche
La portion du tableau, entre les indices gauche et droite, où la valeur cherchée peut encore se trouver.
Borne gauche / borne droite
Les indices gauche et droite qui délimitent l'intervalle de recherche actuel.
Milieu
L'indice au centre de l'intervalle de recherche, calculé par (gauche + droite) // 2.
Division entière (//)
La division dont on ne garde que la partie entière : 5 // 2 = 2 (et non 2,5).
Complexité
Une estimation du nombre d'opérations faites par l'algorithme, en fonction du nombre n de valeurs du tableau.
2. Le tableau d'exemple utilisé dans cette page
On utilise le tableau T, de 6 valeurs, déjà trié :
Indice
0
1
2
3
4
5
Valeur T[i]
1
2
3
5
8
9
C'est justement le tableau obtenu à la fin des fiches sur le tri par sélection et le tri par insertion. La recherche dichotomique a besoin d'un tableau déjà trié pour fonctionner.
But de l'algorithme : chercher la valeur x = 2 dans ce tableau, et renvoyer son indice si elle s'y trouve (ou -1 si elle n'y est pas).
3. Recherche dichotomique
3.1 — Principe, en une phrase
Principe
On compare x à la valeur du milieu de l'intervalle de recherche : si ce n'est pas elle, on élimine la moitié de l'intervalle qui ne peut pas contenir x, et on recommence sur la moitié restante.
3.2 — Les étapes, dans l'ordre exact
On part avec gauche = 0 et droite = n - 1 (tout le tableau est encore possible).
Tant que gauche est inférieur ou égal à droite, on calcule milieu = (gauche + droite) // 2.
Si T[milieu] est égal à x, on a trouvé : on renvoie milieu.
Si T[milieu] est plus petit que x, alors x ne peut être qu'à droite de milieu (si x est présent) : on met gauche = milieu + 1.
Si T[milieu] est plus grand que x, alors x ne peut être qu'à gauche de milieu (si x est présent) : on met droite = milieu - 1.
On répète les étapes 2 à 5. Si on arrive à gauche supérieur à droite sans avoir trouvé x, c'est que x n'est pas dans le tableau : on renvoie -1.
3.3 — Démonstration interactive
intervalle de recherche actuelindices déjà exclusindice milieu en cours de testvaleur trouvée
Étape 1 / 1
On cherche x = 2. La ligne de code correspondant à l'étape en cours est surlignée ci-dessous.
3.4 — Code Python
def recherche_dichotomique(T, x): """Cherche x dans le tableau trié T. Renvoie l'indice de x, ou -1 si absent.""" gauche = 0 droite = len(T) - 1 while gauche <= droite: milieu = (gauche + droite) // 2 if T[milieu] == x: return milieu elif T[milieu] < x: gauche = milieu + 1 else: droite = milieu - 1 return -1# Jeu de données : le même tableau trié que les fiches précédentesT = [1, 2, 3, 5, 8, 9]print(recherche_dichotomique(T, 2))# Résultat affiché : 1
3.5 — Nombre de comparaisons et complexité
À chaque étape, l'intervalle de recherche est divisé par deux : c'est pour cela que l'algorithme s'appelle « dichotomique » (« couper en deux »).
Pour notre exemple (n = 6), il faut au maximum 3 comparaisons pour trouver une valeur, ou pour être sûr qu'elle n'est pas dans le tableau.
Si x n'est pas dans le tableau, l'algorithme s'arrête quand même : dès que gauche devient supérieur à droite, la boucle s'arrête et on renvoie -1.
Complexité : O(log n). C'est beaucoup plus rapide qu'une recherche séquentielle (qui examine les valeurs une par une, en O(n)) — mais uniquement possible sur un tableau trié.