Exo bac C7.EB1

On donne ci-dessous le code de la fonction de recherche dichotomique d'un élément dans une liste.

def rechercheDicho (elem, liste):
    """
    Cette fonction indique si un élément se trouve dans un tableau.
    Elle utilise la méthode de recherche dichotomique.
    Elle prend en arguments :
      - elem : élément à rechercher de type string ;
      - liste : liste d'éléments de type string triée par ordre croissant.
    Elle renvoie un booléen indiquant à la présence ou non de l'élément.
    """
    deb = 0
    fin = len(liste) - 1
    m = (deb + fin) // 2
    while deb <= fin:
        if liste[m] == elem:
            return True
        elif liste[m] > elem:
            fin = m - 1
        else:
            deb = m + 1
        m = (deb + fin) // 2
    return False

Partie A : La recherche dichotomique

1) La recherche dichotomique d'un élément dans un tableau ne peut se faire que si le tableau est trié.

2) Le coût (la complexité) d'un algorithme de recherche dichotomique est :

3) Justifier pourquoi l'entier fin-deb est un variant de boucle qui montre la terminaison du programme de recherche dichotomique.

Partie B : La recherche dichotomique itérative

Dans l'ensemble de cette partie, on considère la liste : Lnoms = ["alice", "bob", "etienne", "hector", "lea", "nathan", "paul"].

1) Expliquer pourquoi à la ligne 11, on a « fin = len(liste) - 1 » plutôt que « fin = 6 ».

2) En Python, l'opérateur // donne le quotient de la division euclidienne de deux nombres entiers.
Proposer un algorithme pour obtenir ce quotient, sans utiliser l'opérateur //.

3) Donner la trace complète de l'exécution de rechercheDicho("lea", Lnoms) en complétant le tableau ci-dessous sur votre copie :

4) Sur votre copie, modifier le code du corps de la fonction rechercheDicho() pourqu'elle renvoie aussi la position (l'indice) de l'élément cherché ou -1 si l'élément n'est pas trouvé.

Partie C : La recherche dichotomique récursive

1) Donner la définition d'une fonction récursive en programmation.

2) Écrire en langage naturel ou en python, l'algorithme de recherche dichotomique d'un élément dans une liste, triée de façon croissante, en utilisant une méthode récursive. Il renverra True si l'objet a été trouvé, False sinon.