Recherche dans une liste, 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.

//déclarations val: Valeur cherchée (entier) i: Entier liste : liste de N entiers triés retour : Booléen //initialisation retour ← faux i ← 0 //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 i <= N et retour est faux: si liste[i] == val: retour ← vrai i ← i+1 //Affichage du résultat Si retour == vrai: Afficher "La valeur ", val , " est dans la liste." Sinon: Afficher "La valeur ", val , " n'est pas dans la liste."

Implémentez la recherche naîve en Python de manière itérative. Pour cela écrire le script de la fonction naiveSearch(lst, val)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.

Puis tester les valeurs 3, 12, 48 et 4 avec la liste: ma_liste=[3,5,12,15,48]

Code de déblocage de la correction :

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

Code de déblocage de la correction :

On voit que cet algorithme n'est peut-être pas le plus pertinant, car dans le pire des cas, c'est à dire le cas ou l'élement cherché n'est pas présent, on devra parcourir toute la liste.

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.

Méthode et exemple pas à pas

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

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.

Image non trouvée !?

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)

Image non trouvée !?

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)

Image non trouvée !?

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

  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.

    Code de déblocage de la correction :

  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.

    Code de déblocage de la correction :

L'algorithme

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

//déclarations indice_gauche, indice_droite, elmt, indice_centre: Entiers liste : liste de N entiers triés retour : Booléen //initialisation indice_gauche ← 0 indice_droite ← N-1 retour ← faux //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 retour != vrai et indice_gauche <= indice_droite: indice_centre ← partie_entière((indice_gauche + indice_droite)/2) si liste[indice_centre] == val: retour ← vrai sinon: si val > liste[indice_centre]: indice_gauche ← indice_centre+1 sinon: indice_droit ← indice_centre-1 //Affichage du résultat Si retour == vrai: Afficher "La valeur ", val , " est au rang ", indice_centre Sinon: Afficher "La valeur ", val , " n'est pas dans le tableau."
  1. Ecrire une fonction rechercheDichotomie qui reçoit en paramètre une liste nommée liste et l'élément recherché nommé elmt 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 (cf. accès direct.).

Code de déblocage de la correction :

Voici une liste de prénom d'ami.e.s : liste_amis = ['Ariel','Benjamin','Amir','Melvina','Hector','Zoé','Yasmine','Ursula','Andréa','Marie-Claire','Marc-Aurèle','Jim','Paula' 'Pietro','Xavier','Eléonore','Arthur','Firmin','Alice','Bob','Firdaous','Olga','Shinzo','Li','Mathéo','Rachel','Philippine','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.

Code de déblocage de la correction :

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.

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

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

Ecrire une fonction nb_de_tours(n) qui renvoie le plus petit entier $k$ tel que $2k > 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 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é !".

Variant de boucle

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. longueur est appelé un variant de boucle.

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

Un variant de boucle sert à prouver la terminaison d'une boucle, c'est-à-dire que l’on sort nécessairement de la boucle au boût d’un nombre fini d’itérations.

Comme longueur décroit à chaque boucle, debut <=fin ??? finira par être faux. Longueur est appelé un variant de boucle.

Afin prouver la terminaison d'une boucle on peut utiliser variant de boucle, c'est-à-dire un entier naturel qui décroit strictement à chaque itération.

On considère longueurn la taille de la sous-liste à l'étape $n$.

Lorsque l'on passe à l'étape $n+1$, il y a trois possibités :

Sitographie

Voici une liste de sites traitant de la dichotomie :

Savoir faire et Savoir

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International