Aller au contenu

TP - Recherche dans une liste⚓︎

1. l'algorithme naïf⚓︎

Pour trouver un nombre dans une liste il suffit de balayer la liste et de renvoyer True dès qu’on trouve l’élément recherché et False si on a parcouru toute la liste sans trouver l’élément.

fonction rechercheNaive(liste, valeurCherchee):
    pour chaque index de la liste:
        si liste[index] est égal à valeurCherchee:
            retourne vrai
    retourne faux // élément non trouvé

Exercice 1

  1. Implémentez la recherche naîve en Python de manière itérative. Pour cela écrire le script de la fonction recherche_naive(lst, val) où lst est une liste d'entier et val la valeurà cherher dans la liste. Cette fonction renvoie True si val est dans la liste lst et False sinon.
  2. Puis tester les valeurs 3, 12, 48 et 4 avec la liste: ma_liste = [3,5,12,15,48]

Exercice 2

  1. Faire le même exercice à l'aide d'un autre type de boucle.

2. La dichotomie: généralités⚓︎

Cette méthode, vous la connaissez tous!

Vous avez probablement joué au jeu :trouve un nombre entre 1 et 100. Vous avez commencé par proposer 50. Si on vous répond, c'est plus, vous proposez 75 puis si l'on vous répond c'est moins vous proposez 62... Vous êtes alors en train d'effectuer une recherche dichotomique !

Faire une recherche dichotomique, c'est chercher une valeur dans un tableau trié en prenant, à chaque étape, le milieu de l'ensemble des valeurs possibles pour éliminer la moitié des possibilités.

2.1 Méthode et exemple pas à pas⚓︎

Soit une liste de nnn objets déjà triés. On recherche un objet en particulier.

  • on choisit dans la liste l'objet médian (une moitié des objets est avant, l'autre moitié est après).
  • on compare les deux objets . Trois cas :
    • si on a trouvé l'objet cherché alors c'est fini.
    • si l'objet recherché est placé avant l'objet médian alors on recommence avec cette première partie de la liste.
    • si l'objet recherché est placé après l'objet médian alors on recommence avec cette seconde partie de la liste.
  • on répète cette démarche jusqu'à ce qu'au bout d'un certain nombre d'essais (cela se calcule) :
    • soit on a trouvé l'objet cherché,
    • soit il n'est pas dans la liste.

Prenons par exemple la liste triée suivante : [1,3,4,6,7,8,10,13,14], où nous allons rechercher par dichotomie l'élement 4

On utilise deux pointeurs indice_gauche et indice_droit pour délimiter la sous-liste sur laquelle porte la recherche courante, au départ il s'agit de la liste entière.

indice_gauche pointe vers l'élément d'indice 0 et indice_droite pointe vers le dernier élément de notre liste qui ici a l'indice 8.

On cherche l'indice indice_centre de l'élément médian en ne gardant que la partie entière de la moyenne indice_gauche et indice_droit, ici \(\frac{0+8}{2}=4\), l`élément médian est donc l'élément d'indice 4, c'est-à-dire l'élément 7.

dicho1

Maintenant on compare l'élément central 7 à l'élément recherché 4 : ici 4 < 7, cela signifie que 4 ce trouve dans la première moitié de la liste (celle avant 7).

On modifie alors la valeur du pointeur indice_droit, qui prend la valeur de indice_centre-1, et on recommence avec cette nouvelle sous-liste.

indice_gauche = 0 ; indice_droit= 3 et indice_centre=1 (partie entière de \(\frac{0+3}{2}\), c'est-à-dire de 1.5)

dicho2

Maintenant on compare l'élément central 3 à l'élément recherché 4 : ici 4 > 3, cela signifie que que 4 ce trouve dans la deuxième moitié de la sous-liste (celle après 3).

On modifie alors la valeur du poiteur indice_gauche, qui prend la valeur de indice_centre+1, et on recommence avec cette nouvelle sous-liste.

indice_gauche = 2 ; indice_droit= 3 et indice_centre=2 (partie entière de \(\frac{2+3}{2}\), c'est-à-dire de 2.5)

dicho3

Maintenant on compare l'élément central 4 à l'élément recherché 4 : ici 4 = 4, l'élément recherché est présent.

Si la sous-liste devient vide, c'est-à-dire que le pointeurs indice_gauche devient supérieur au pointeur indice_droit, la recherche est infructueuse et l'algorithme s'arrête

Exercice 3

  1. Décrivez chacune des étapes de progression de la recherche dichotomique de l'élément 35 appliquée à la liste ordonnée [2, 12, 17, 25, 33, 35, 44, 54, 77, 91] puis indiquez le nombre de comparaisons nécessaires à cette recherche.

  2. Décrivez chacune des étapes de progression de la recherche dichotomique de l'élément 50 appliquée à la liste ordonnée [2, 12, 17, 25, 33, 35, 44, 54, 77, 91] puis indiquez le nombre de comparaisons nécessaires à cette recherche.

2.2 L'algorithme⚓︎

Voici le pseudo-code en langage naturel de cet algorithme :

fonction rechercheDichotomique(liste, val):
    //initialisation
    indice_gauche ← 0 
    indice_droite ← longueur de liste - 1

    //Boucle de recherche
    // La condition début inférieur ou égal à  fin permet d'éviter de faire
    // une boucle infinie si 'val' n'existe pas dans le tableau.
    Tant que indice_gauche <= indice_droite:
      indice_centre ← partie_entière((indice_gauche + indice_droite)/2)
      si liste[indice_centre] == val:
         retourne vrai
      sinon:
         si val > liste[indice_centre]:
            indice_gauche ← indice_centre + 1
         sinon:
            indice_droit ← indice_centre - 1
    retourne faux

Exercice 4

  1. Ecrire une fonction recherche_dichotomique qui reçoit en paramètre une liste nommée lst et l'élément recherché nommé elm et qui retourne un booléen en fonction de la présence ou non de l'élément recherché.
  2. Testez votre script avec les deux exemples traités dans l'exercice 1

Exercice 5

Voici une liste de prénom d'ami.e.s : 

liste_amis = ['Ariel','Mehdi','Amir','Melvina','Hector','Zoé','Yasmine','Ursula','Andréa','Marie-Claire','Marc-Aurèle','Jim','Paula' 'Pietro','Xavier','Norah','Arthur','Firmin','Alice','Bob','Firdaous','Olga','Shinzo','Li','Mathéo','Rachel','Sabrina','Tao']

  1. Trier par ordre croissant cette liste liste_amis.

  2. Utilisez votre programme de l'exercice 4 afin de savoir si 'Paulo' fait partie de la liste liste_amis.

  3. Utilisez votre programme de l'exercice 4 afin de savoir si 'Yasmine' fait partie de la liste liste_amis.

2.3 Complexité⚓︎

Nous avons vu précédement que l'algorithme naïf de recherche d'un nombre dans une liste triée avait dans le pire des cas une complexité linéaire. Voyons si la dichotomie est plus avantageuse de ce point de vu.

Exercice 6

Déterminez le nombre maximal de comparaisons nécessaires à la recherche d'un élément dans une liste, en complétant le tableau ci-dessous.

Taille de la liste 0 1 2 4 8 16 32 64 128 N
Recherche séquentielle
Recherche dichotomique

Exercice 7

Ecrire 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\).

Saisir en argument successivement plusieurs puissances de 2. Que remarquez-vous quant au résultat affiché ?

Exercice 8

Exercice pour les plus rapides ? Qui reprend le jeu introductif.

Ecrire un programme qui permette à l'ordinateur de jouer contre l'utilisateur pour retrouver un nombre. L'utilisateur choisira un nombre entre 0 et 100 et l'ordinateur devra le trouver, le plus efficacement possible. A chaque proposition faite par l'ordinateur, l'utilisateur devra donner une réponse sous la forme d'une chaine de caractères codant explicitement les notions de "plus grand", "plus petit" ou "bravo, tu as trouvé !".

2.4 Terminaison⚓︎

Dans l'algorithme précédent, nous avons une boucle, nous devons donc nous interroger sur la terminaison de cet algorithme.

Dans la boucle tant que, il y a la condition indice_gauche <= indice_droite qui nous indique que la liste n'est pas vide. On va s'intéresser à la variable longueur = indice_droite - indice_gauche qui est un entier. En utilisant cette nouvelle variable, la condition indice_gauche <= indice_droite devient longueur >= 0.

Variant de boucle

On appelle variant de boucle une quantité entière qui :

  • est positive ou nulle lorsque l'on reste dans la boucle;
  • décroît strictement à chaque itération de la boucle.

Un variant de boucle sert à prouver la terminaison d'une boucle, c'est-à-dire que l’on sort nécessairement de la boucle au bout d’un nombre fini d’itérations puisqu'un entier positif ne peut décroître infiniment.

Preuve de terminaison

Positif ou nul: comme longueur est la différence de l'indice de droite et de l'indice de gauche, c'est une quantité positive ou nulle.

Décroissant: On commence par définir indice_centre ← partie_entière((indice_gauche + indice_droite)/2). A chaque passage dans la boucle, il y a trois cas possibles:

  • si liste[indice_centre] == val, on sort directement de la boucle. La terminaison est assurée.
  • si liste[indice_centre] > val, on modifie la valeur de droite. En appelant indice_droite2 cette nouvelle valeur, on a : indice_droite2 - indice_gauche < indice_centre - indice_gauche <= indice_droite - indice_gauche car indice_droite2 = indice_centre - 1 < indice_centre Ainsi, le variant a strictement décru.
  • sinon, on modifie gauche et on a de même : indice_droite - indice_gauche2 < indice_droite - indice_centre <= indice_droite - indice_gauche. De même, le variant a strictement décru.

Donc longueur est bien un variant de boucle et algorithme termine bien.

sources : - https://www.monlyceenumerique.fr/nsi_premiere/algo_a/a5_dichotomie.php