1NSI : TD - Recherche Dichotomique dans un Tableau Trié⚓︎
Dans un tableau (quelconque) NON TRIÉ \(A=[A[0], A[1],...,A[n-1]]\) contenant \(n\) valeurs, nous savons que la recherche de l'occurence d'une valeur cible \(C\) dans \(A\), est un algorithme de complexité en temps linéaire, càd en \(O(n)\).
La question qui se pose ici, est de savoir:
Problématique
Si de plus le tableau \(A=[A[0], A[1],...,A[n-1]]\) est déjà TRIÉ, alors peut-on espérer améliorer la complexité en temps de l'algorithme de recherche d'une occurence?
Introduction⚓︎
On se donne donc un tableau (déjà) TRIÉ \(A=[A[0], A[1],...,A[n-1]]\) de \(n\) valeurs (par exemple dans le sens croissant), c'est-à-dire que :
On souhaite déterminer une occurence d'une certaine valeur cible notée \(C\) dans ce tableau \(A\) (en pratique son indice dans le tableau), c'est-à-dire savoir si elle se trouve dans ce tableau \(A\), ou PAS, mais en tirant profit de l'information supplémentaire que le tableau est trié (dans le sens croissant par exemple).
Une Introduction Vidéo (\(\approx 11 min\))⚓︎
Algorithme en pseudo-code⚓︎
# Recherche Dichotomique de l'occurence d'une valeur C dans un tableau A TRIÉ
fonction recherche_dico(C,A):
n prend la valeur taille(A)
gauche prend la valeur 0
droite prend la valeur n - 1
Tant que gauche ≤ droite:
milieu prend la valeur partie entière de [(Gauche + Droite) / 2]
Si C > A[milieu] Alors:
gauche = milieu + 1
Sinon Si C < A[milieu] Alors:
droite = milieu - 1
Sinon:
retourner milieu
retourner Vide
Questions : Python, Terminaison, Correction, Complexité⚓︎
-
Implémenter cet algorithme en Python
Corrigé
1 2 3 4 5 6 7 8 9 10 11 12 13
def recherche_dico(C,A): n = len(A) gauche = 0 droite = n-1 while gauche <= droite: milieu = (gauche + droite)//2 if C > A[milieu]: gauche = milieu + 1 elif C < A[milieu]: droite = milieu - 1 else: # trouvé! return milieu return None
-
Étudier la terminaison de cet algorithme. On pourra commencer par déterminer un variant de boucle.
Corrigé
On note \(v=droite-gauche+1\):
- \(v\) est un nombre entier
- \(v\) est strictement positif au début, car au début de l'algo, \(droite-gauche=(indice \, de) \, droite-0=droite \ge 0\) donc \(v=droite-gauche+1 \ge 0+1 = 1>0\)
- \(v=droite-gauche+1\) décroit d'au moins un cran à chaque itération, car :
- ou bien c'est la gauche qui augmente d'au moins 1 cran (Ligne 10), car \(milieu+1\ge gauche+1\), et pendant ce temps la droite est inchangée. Donc \(v=droite-gauche+1\) baisse d'au moins 1 cran (car on enlève davantage)
- ou bien c'est la droite qui baisse d'au moins 1 cran (Ligne 13), car \(milieu-1\le droite-1\), et pendant ce temps la gauche est inchangée. Donc \(v=droite-gauche+1\) baisse d'au moins 1 cran.
- ou bien on a trouvé la bonne solution (ligne 7)
- la condition \(v\le 0 \Leftrightarrow droite-gauche+1 \le 0 \Leftrightarrow droite -gauche \le -1 <0\) correspond bien à la sortie de la boucle
-
Étudier la correction de cet algorithme. On pourra commencer par déterminer un invariant de boucle.
Corrigé
1 2 3 4 5 6 7 8 9 10 11 12 13
def recherche_dico(C,A): n = len(A) gauche = 0 droite = n-1 while gauche <= droite: milieu = (gauche + droite)//2 if C > A[milieu]: gauche = milieu + 1 elif C < A[milieu]: droite = milieu - 1 else: # ici, C= A[milieu] forcément --> donc trouvé! return milieu return None
Notons provisoirement
g=gauche
,d=droite
etm=milieu
.
L'algorithme est plus subtil qu'il n'y paraît de prime abord.Les Bornes restent entre 0 et la taille initiale
Commençons par montrer que l'algorithme ne va pas échouer en raison d'un dépassement (trop à gauche ou trop à droite) des bornes du tableau A :- Tout d'abord, remarquons que chacune des inégalités
g>=0
etd <= n-1
est un invariant de boucle - Ensuite, à l'intérieur de la boucle (puisque
g <= d
, on a toujours :0 <= g <= d <= n-1
- Enfin, le tableau
L
n'est accédé que par la valeur dem=(g+d)//2
qui est le milieu de gauche et droite (arrondi à l'entier inférieur), ce qui garantit un accès légal au tableau
Démonstration de la Correction
On noteInv : « la valeurC
ne peut se trouver que dansA[g..d]
». Montrons qu'il s'agit bien d'uninvariant de boucle :Initialisation : Inv est vrai initialement, car on a initialisé les variables àg=0
etd=n-1
Hérédité/Conservation : Supposons que Inv soit vrai en entrant dans une certaine itération :- Si
g
est modifié, parg=m+1
alors l'invariant Inv est préservé, car le tableau est trié etC>A[m]
- Si
d
est modifié, pard=m-1
alors l'invariant Inv est préservé, car le tableau est trié etC<A[m]
- Il y a donc bien conservation en fin d'itération, donc en début de la suivante
- Si
Terminaison :- soit, durant une certaine itération, on renvoie un entier
m
(ligne 12) qui vérifie alors obligatoirementA[m]=C
d'après les 2 tests précédents (à la ligne 7 et ligne 9), doncm
est bien le bon indice correspondant àC
dansA
. Ceci prouve que l'algorithme est correct dans le cas où la valeur cibleC
appartienne bien au tableauA
. - soit, on renvoie
None
: Remarquons que dans ce cas on est obligatoirement allé jusqu'au bout de la bouclewhile
le plus longtemps possible, et que dans ce cas forcément, on avaitg=d
durant le dernier tour (sinon, si on avaitd>=g+1
, alors on aurait pu refaire encore un tour). De plus, on sait d'après l'hérédité queC
se trouve obligatoirement dansA[g..d]=L[g..g]
, ceci prouve que si on renvoieNone
, c'est que ce dernier test a échoué durant la dernier itération (doncC!= A[g]
etA[g]
était la dernière valeur restante à tester). Ensuite, on sort de la boucle (en incrémentantg
de 1, ou décrémentantd
de 1 selon la situation) pour parvenir à la ligne \(13\). Cela prouve donc que la valeur cibleC
n'appartient pas au tableauL
, et donc que l'algorithme est correct dans le cas où la valeurC
n'appartienne pas au tableauA
.
- soit, durant une certaine itération, on renvoie un entier
- Tout d'abord, remarquons que chacune des inégalités
-
Étudier la complexité en temps de cet algorithme:
La taille \(n\) des données en entrée est le nombre d'éléments du tableau.
Nous noterons encoreg=gauche
,d=droite
etm=milieu
-
dans le meilleur des cas:
Corrigé
dans le meilleur des cas, on trouve le nombre cible
C
à la première itération, donc dans le meilleur des cas, la complexité en temps est constante, en \(O(1)\) -
dans le pire des cas:
Corrigé
1 2 3 4 5 6 7 8 9 10 11 12 13
def recherche_dico(C,A): n = len(A) gauche = 0 droite = n-1 while gauche <= droite: milieu = (gauche + droite)//2 if C > A[milieu]: gauche = milieu + 1 elif C < A[milieu]: droite = milieu - 1 else: # ici, C= A[milieu] forcément --> donc trouvé! return milieu return None
Nous allons montrer qu'à chaque nouvelle itération (en supposant qu'on ne trouve pas
C
au milieu à cette itération), on divise par \(2\) le nombre de possibilités restantes à tester (en arrondissant à l'entier directement inférieur).Notons provisoirement
\(n=d-g+1\) le nombre d'éléments dansL[g..d]
, càd le nombre d'éléments restants à tester à une certaine itération.- Ou bien, la valeur
C
est la valeur au milieu entreg
etd
, càd queC
est la valeur cible et elle sera trouvée à l'itération suivante. Cela correspond au cas oùC = L[m]
oùm=(g+d)//2
. Dans ce cas, pas besoin d'étudier la diminution de la taille du tableau des éléments restants à traiter entre eux itérations, puisque l'algorithme s'arrête à l'itération suivante. Nous supposerons que nous ne sommes pas dans ce cas. - Ou bien
C
n'est pas la valeur située au milieu deg
etd
(càd supposons queC!=L[m]
avecm = (g+d)//2
), il ne reste alors plus que deux possiblités:- soit
C>L[m]
auquel casC
se trouve forcément dansL[m+1..d]
, donc le nombre d'éléments restants au tour suivant est un nombre entier \(n'\) tel que \(n'=d-(m+1)+1=d-m\). Ensuite, De deux choses l'une:- Ou bien \(n=d-g+1=2p\) est un nombre pair, auquel cas, \(n'=d-m=\dfrac{n}{2}=p \leq \dfrac{n}{2}\)
- Ou bien \(n=d-g+1=2p+1\) est un nombre impair, auquel cas, \(n'=d-m=\dfrac{n-1}{2}=p \leq \dfrac{n}{2}\) Dans tous les cas (pair ou impair), au tour suivant, il reste au maximum \(\dfrac{n}{2}\) : La taille des éléments à tester a donc été divisée par \(2\)
- soit
C<L[m]
auquel casC
se trouve forcément dansL[g..m-1]
, donc le nombre d'éléments restants au tour suivant est un nombre entier \(n'\) tel que \(n'=(m-1)-g+1=m-g\). Ensuite, De deux choses l'une:- Ou bien \(n=d-g+1=2p\) est un nombre pair, auquel cas, \(n'=m-g\lt \dfrac{n}{2}\)
- Ou bien \(n=d-g+1=2p+1\) est un nombre impair, auquel cas, \(n'=m-g=\dfrac{n-1}{2}=p \leq \dfrac{n}{2}\) Dans tous les cas (pair ou impair), au tour suivant, il reste au maximum \(\dfrac{n}{2}\) nombres à traiter: La taille des éléments à tester a donc été divisée par \(2\) à chaque nouvelle itération.
- Conclusion : Le nombre d'éléments restants à tester à l'itération suivante a été divisé par \(2\) par rapport à l'itération précédente.
- soit
- Notons \(n\) la taille des données en entrée de l'algorithme, càd le nombre d'éléments (déjà triés) dans le tableau initial, et
\(C(n)\) la complexité/coût en temps de l'algorithme, càd le nombre total d'itérations à réaliser pour terminer l'algorithme. Le résultat précédent montre que \(C(n)\) vérifie la relation: \(C(n)=C\left( \dfrac{n}{2} \right)+1\), ou ce qui revient au même :
\(C(2n)=C(n)+1\)
D'après lemaster theorem , on sait que cette relation correspond à unecomplexité logarithmique , en \(O(log_2(n))\) : il s'agit donc d'unerecherche rapide - dans le cas moyen: (à faire)
Comparer ces \(3\) complexités, en particulier sont-elles égales?
Corrigé
NON, elles ne sont pas toutes égales
- Ou bien, la valeur
-
-
Étudier la complexité en espace de cet algorithme
Corrigé
On n'as pas besoin de tableaux supplémentaires, seul un nombre constant de variables (3) est utilisé: La complexité en espace est constante, en \(O(1)\)