Exercices

Exercice n°1 : Recherche dichotomique

Question 1 : La fonction

À l'aide de l'algorithme décrit en cours, rédiger la fonction Python recherche_dichotomique(l, v) qui renvoie True si v est dans l, et False sinon.

Vous devrez rédiger les docstrings et doctests adéquats.

Une info ?

On devra utiliser une boucle while. Repérez la condition à respecter pour continuer à faire le tour de la boucle.

Solution

def recherche_dichotomique(l, v):
    """
    Recherche v dans l en utilisant l'algorithme de recherche dichotomique
    Entrées : l - list : Liste triée d'éléments
              v : Objet à rechercher dans la liste
    Sortie : bool - True si v est dans l, False sinon
    >>> recherche_dichotomique([1,2,3,4,5,6], 3)
    True
    >>> recherche_dichotomique([1,3,4,6,7,9,10], 2)
    False
    """
    g = 0
    d = len(l)-1

    while g <= d:
        m = (g+d)//2

        if l[m] == v:
            return True
        elif l[m] < v:
            g = m + 1
        else:
            d = m - 1
    return False

Question 2 : Améliorer

Améliorez votre fonction afin de renvoyer l'indice de la valeur si elle est trouvée. Sinon, vous devrez renvoyer None. Mettre à jour les docstrings et doctests en conséquence.

Exercice n°2 : Vérifier l'optimalité

Dans cet exercice, on souhaite vérifier que la méthode de recherche dichotomique est réellement efficace. En effet, peut-être que couper au début ou à la fin de la liste est plus optimal que couper au milieu.

Question 1 : La fonction

Pour cela, commencer par rédiger une fonction recherche(l, v, c) qui recherche la valeur v dans l mais qui coupe à une valeur c comprise strictement entre 0 et 1. Par exemple, si c=0.5, alors cela revient à couper au milieu, comme l'algorithme de recherche dichotomique.

La fonction devra renvoyer le nombre d'itérations de la boucle while (autrement dit, le nombre de découpes effectuées).

Boucle infinie ?

Si vous tombez sur une boucle infinie, vous avez probablement un problème avec votre valeur de m. Vérifiez qu'elle ne soit pas en dehors des bornes g et d.

Question 2 : Les tests

Une fois votre fonction mise en place, testez-la avec différentes valeurs de c (par exemple 0.1, 0.2, ..., 0.9) pour plusieurs listes aléatoires. Compilez ces résultats dans un graphique affichant en abscisse les valeurs de c et en ordonnée le nombre moyen de découpes par appel de fonction.