Lycée > Premiere > NSI > L'algorithme de recherche dichotomique dans un tableau trié

L'algorithme de recherche dichotomique dans un tableau trié

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Comprendre l’algorithme de recherche dichotomique dans un tableau trié.
Étudier la terminaison et la correction de cet algorithme.

Points clés

La recherche dichotomique est un algorithme de recherche qui permet de déterminer la position d’un élément dans un tableau trié. Cet algorithme compare la valeur recherchée à la valeur du milieu du tableau.
Un variant de boucle est une valeur entière qui répond à deux critères. La valeur doit être positive ou nulle, et être strictement décroissante. Ce variant permet de prouver la terminaison, c’est-à-dire de vérifier que le programme s’arrêtera.
Un invariant de boucle est une proposition qui doit être vraie à chaque itération de l’algorithme. Cet invariant permet de prouver la correction, c’est-à-dire de vérifier que le programme retournera bien ce que l’on veut.

Pour bien comprendre

Parcourir un tableau.
Utiliser les structures conditionnelles.

On va considérer un tableau trié dans l’ordre croissant, mais tout ce qui suit fonctionne également pour un tri dans l’ordre décroissant.

1. L’algorithme de recherche dichotomique

a. Principe

La recherche dichotomique est un algorithme de recherche qui permet de déterminer la position d’un élément dans un tableau trié.

Cet algorithme compare la valeur recherchée à la valeur du milieu du tableau.

Si c’est la valeur recherchée, on s’arrête et on retourne sa position.
Si cette valeur est plus petite, alors la valeur recherchée est située dans la partie gauche du tableau, sinon elle est dans la partie droite.

On répète le procédé de comparaison jusqu’à ce que l’on obtienne la valeur recherchée, ou jusqu’à ce que l’on ait réduit l’intervalle de recherche à un intervalle vide : cela signifie que la valeur recherchée n’est pas présente dans le tableau.

À chaque étape, la zone de recherche de la valeur est divisée par deux.

b. Programmation en Python 3

On va écrire un programme Python qui retourne la position de l’élément x si celui-ci se trouve dans le tableau, et None si l’élément ne s’y trouve pas.

Exemple – Recherche dichotomique sur t=[3,5,7,8]
Le programme devra retourner 1 pour x=5.
Le programme devra retourner None pour x=90.

On utilise deux variables gauche et droite pour écrire le programme qu’on initialise pour délimiter l’intégralité du tableau.

En Python, la fonction dichotomie(t, v) implémente la recherche dichotomique de la valeur v par rapport au tableau t.

def dichotomie(t, v):	On définit la fonction dichotomie.
gauche = 0	On initialise la variable gauche.
droite = len(t) - 1	On initialise la variable droite.
while gauche <= droite:	Tant que l’indicateur droite est supérieur à gauche, on continue.
milieu = (gauche + droite) // 2	On prend l’indice du milieu.
if t[milieu] == v:	Si la valeur recherchée v est égale à la valeur du milieu du tableau,
return milieu	alors on retourne l’indice.
elif t[milieu] > v:	Si la valeur recherchée v est supérieure à la valeur du milieu du tableau,
droite = milieu - 1	alors on décrémente l’indice droite.
else:	Sinon,
gauche = milieu + 1	on incrémente l’indice gauche.
return None	On retourne None.

2. Terminaison et correction de l’algorithme

a. Terminaison

Étudier la terminaison d’un algorithme revient à déterminer s’il s’arrêtera (quelles que soient les données utilisées).

L’algorithme de la recherche dichotomique contient une boucle non bornée while, il faut s’assurer que cette boucle s’arrête.

Variant de boucle

On doit pour cela trouver un variant de boucle.

Un variant de boucle est une valeur entière qui répond à deux critères.
La valeur doit :

être positive ou nulle ;
être strictement décroissante.

Si on trouve un variant de boucle, on va obligatoirement sortir de la boucle au bout d’un nombre fini d’étapes.

Application à l’algorithme

La valeur « droite – gauche » est positive ou nulle au départ de la boucle car on a while gauche <= droite.

On va montrer que la valeur « droite – gauche » décroit strictement à chaque itération.

Si t[milieu] == v, alors on sort de la boucle.
Si t[milieu] > v, alors gauche devient gauche+1, donc le variant décroit strictement (la gauche du tableau se rapproche de la droite).
Si t[milieu] < v, alors droite devient droite–1, donc le variant décroit strictement (la droite du tableau se rapproche de la gauche).

On a donc bien un variant de boucle, le programme se termine car la boucle se termine toujours.

b. Correction

Démontrer la correction d’un algorithme revient à déterminer s’il retourne bien ce que l’on veut.

Pour prouver la correction de cet algorithme, on va utiliser la technique de l’invariant de boucle.

Un invariant de boucle est une proposition qui doit être vraie à chaque itération de l’algorithme.

Un invariant de boucle peut être : « Si v (la valeur recherchée) est dans t (le tableau), son indice est compris entre gauche et droite. »

Démonstration de la correction

Si la propriété est vraie en entrée de boucle, alors il n’y a que trois possibilités.

Si t[milieu] == v, alors on sort de la boucle.
Si t[milieu] > v, alors la recherche se poursuit de gauche à milieu–1, la propriété est donc encore vraie.
Si t[milieu] < v, alors la recherche se poursuit de milieu+1 à droite, la propriété est donc encore vraie.

On a donc bien un invariant de boucle et l’algorithme fait bien ce que l’on veut dans le cas où la recherche aboutit.