Recherche dichotomique

Voici l'algorithme de recherche dichotomique vu dans le cours

In [1]:
def recherche_dichotomique(v, T):
    """renvoie une position de v dans le tableau T, supposé trié,
    et None si v ne s'y trouve pas"""
    g = 0
    d = len(T) - 1
    while g <= d:
        m = (g + d) // 2
        if v < T[m]:
            d = m - 1
        elif v > T[m]:
            g = m + 1
        else:
            return m
    return None

Exercice 1

Quelles sont les instructions à écrire pour vérifier vos réponses aux exercices 9 et 10 ?

In [ ]:

Exercice 2

  1. Modifiez la fonction recherche_dichotomique(v, T) pour afficher le nombre total de tours de boucle effectués par l'algorithme.
In [ ]:
  1. Lancez le programme sur des tableaux de taille différentes (par exemple, 100, 1000, etc.) et observez le nombre de tours affichés. On pourra par exemple chercher la valeur 1 dans un tableau ne contenant que des valeurs 0, ce qui correspond au pire cas.
In [ ]:

Exercice 3

Ecrivez une fonction nb_de_tours(n) qui renvoie le plus petit entier k tel que 2^k > n, c'est-à-dire le nombre maximal de valeurs examinées par la recherche dichotomique dans un tableau de taille n.

In [ ]: