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 : \(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 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é

1. Implémenter cet algorithme en Python
2. Étudier la terminaison de cet algorithme. On pourra commencer par déterminer un variant de boucle
3. Étudier la correction de cet algorithme. On pourra commencer par déterminer un invariant de boucle

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
   • dans le pire des cas
   • dans le cas moyen

   Comparer ces \(3\) complexités, en particulier sont-elles égales?

5. Étudier la complexité en espace de cet algorithme