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:

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 : $A[0]\le A[1]\le ...\le A[n-1]$
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 11min$)⚓︎

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é⚓︎

1. 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

2. É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=(indicede)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\iff droite-gauche+1\le 0\iff droite-gauche\le -1<0$ correspond bien à la sortie de la boucle

3. É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 et m=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 et d <= 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 de m=(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 note Inv : « la valeur C ne peut se trouver que dans A[g..d] ». Montrons qu'il s'agit bien d'un invariant de boucle :

   • Initialisation : Inv est vrai initialement, car on a initialisé les variables à g=0 et d=n-1
   • Hérédité/Conservation : Supposons que Inv soit vrai en entrant dans une certaine itération :
     • Si g est modifié, par g=m+1 alors l'invariant Inv est préservé, car le tableau est trié et C>A[m]
     • Si d est modifié, par d=m-1 alors l'invariant Inv est préservé, car le tableau est trié et C<A[m]
     • Il y a donc bien conservation en fin d'itération, donc en début de la suivante
   • Terminaison :
     • soit, durant une certaine itération, on renvoie un entier m (ligne 12) qui vérifie alors obligatoirement A[m]=C d'après les 2 tests précédents (à la ligne 7 et ligne 9), donc m est bien le bon indice correspondant à C dans A. Ceci prouve que l'algorithme est correct dans le cas où la valeur cible C appartienne bien au tableau A.
     • soit, on renvoie None: Remarquons que dans ce cas on est obligatoirement allé jusqu'au bout de la boucle while le plus longtemps possible, et que dans ce cas forcément, on avait g=d durant le dernier tour (sinon, si on avait d>=g+1, alors on aurait pu refaire encore un tour). De plus, on sait d'après l'hérédité que C se trouve obligatoirement dans A[g..d]=L[g..g], ceci prouve que si on renvoie None, c'est que ce dernier test a échoué durant la dernier itération (donc C!= A[g] et A[g] était la dernière valeur restante à tester). Ensuite, on sort de la boucle (en incrémentant g de 1, ou décrémentant d de 1 selon la situation) pour parvenir à la ligne $13$. Cela prouve donc que la valeur cible C n'appartient pas au tableau L, et donc que l'algorithme est correct dans le cas où la valeur C n'appartienne pas au tableau A.

4. É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 encore g=gauche, d=droite et m=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 dans L[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 entre g et d, càd que C 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 de g et d (càd supposons que C!=L[m] avec m = (g+d)//2), il ne reste alors plus que deux possiblités:
       • soit C>L[m] auquel cas C se trouve forcément dans L[m+1..d], donc le nombre d'éléments restants au tour suivant est un nombre entier $n^{\prime }$ tel que $n^{\prime }=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^{\prime }=d-m={\displaystyle \frac{n}{2}}=p\le {\displaystyle \frac{n}{2}}$
         • Ou bien $n=d-g+1=2p+1$ est un nombre impair, auquel cas, $n^{\prime }=d-m={\displaystyle \frac{n-1}{2}}=p\le {\displaystyle \frac{n}{2}}$ Dans tous les cas (pair ou impair), au tour suivant, il reste au maximum ${\displaystyle \frac{n}{2}}$ : La taille des éléments à tester a donc été divisée par $2$
       • soit C<L[m] auquel cas C se trouve forcément dans L[g..m-1], donc le nombre d'éléments restants au tour suivant est un nombre entier $n^{\prime }$ tel que $n^{\prime }=(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^{\prime }=m-g<{\displaystyle \frac{n}{2}}$
         • Ou bien $n=d-g+1=2p+1$ est un nombre impair, auquel cas, $n^{\prime }=m-g={\displaystyle \frac{n-1}{2}}=p\le {\displaystyle \frac{n}{2}}$ Dans tous les cas (pair ou impair), au tour suivant, il reste au maximum ${\displaystyle \frac{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.
     • 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({\displaystyle \frac{n}{2}}\right)+1$, ou ce qui revient au même :
       $C(2n)=C(n)+1$
       D'après le master theorem, on sait que cette relation correspond à une complexité logarithmique, en $O(lo{g}_2(n))$ : il s'agit donc d'une recherche rapide
     • dans le cas moyen: (à faire)

     Comparer ces $3$ complexités, en particulier sont-elles égales?

     Corrigé

     NON, elles ne sont pas toutes égales

5. É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)$