Comme les autres opérations sur les tableaux (insertion, modification, suppression), l’opération de recherche est une opération très importante et très récurrente. La plus part des programmes qui utilisent les tableaux doivent utiliser l’opération de recherche.
Dans cette partie de cours, on commence par le type de recherche dit : recherche séquentielle. par la suite, on découvre un autre type de recherche qui est : la recherche dichotomique.
1- Opération de recherche : recherche séquentielle
Il s’agit de rechercher un élément séquentiellement à partir de la première position du tableau.
Supposons, on a un tableau T[100] des réels, l’utilisateur saisit une valeur , puis le programme affiche ‘existe’ ou ‘n’existe pas’ selon le cas (si la valeur existe dans le tableau, on affiche ‘existe’, sinon, on affiche n’existe pas.)
Solution Algo_Ex01: tableaux T(100): entier variables s, i: entier existe : booleen debut existe <-0 //Remplissage du tableau ecrire "donner un valeur" lire s #boucle de recherche pour i allant de 1 à 100 faire Si ( s==T(i)) alors écrire "existence" existe<-1 #arreter la recherche i<-101 fin Si fin pour # fin de la recherche si existe =0 alors ecrire "n’existe pas" fin si Fin
2-Recherche séquentielle dans un tableau ordonné (ordre croissant)
Il s’agit de rechercher un élément séquentiellement à partir de la première position du tableau. De plus, si on rencontre un élément supérieur à l’élément recherché, on arrête le parcours du tableau.
Algorithme :
supposons, on a un tableau T[100] des réels, l’utilisateur saisit une valeur , puis le programme affiche ‘existe’ ou ‘n’existe pas’ selon le cas (si la valeur existe dans le tableau, on affiche ‘existe’, sinon, on affiche n’existe pas.)
Solution : Algo_Ex tableaux T(100): entier variables s, i: entier existe : booleen debut existe <-0 # Remplissage de tableau ecrire "donner un valeur" lire s #boucle de recherche pour i allant de 1 à 100 faire Si ( s == T(i) )alors ecrire"existence" existe<-1 #arreter la recherche i<-101 fin Si si ( s > T(i) ) alors i<-101 finsi fin pour # fin de la recherche si existe =0 alors ecrire "n’existe pas" fin si Fin
3- Opération de recherche : recherche dichotomique
La recherche dichotomique, ou recherche par dichotomie1 (en anglais : binary search), est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié (le tableau est ordonné). Le principe est le suivant :
On utilise 3 variables : Bi, Bs et Milieu, représentant respectivement la borne inférieure, la borne supérieure et l’indice du milieu, c’est à dire (Bi + Bs) /2.
- Initialement Bi est 1 et Bs est M (taille du tableau)
- Considérons la valeur se trouvant au milieu du tableau T[Bi ..Bs] c’est à dire V[Milieu]. Si V[Milieu] est la donnée recherchée, la recherche se termine avec succès
Autrement, comme le tableau est ordonné, à ce niveau on peut orienter la recherche uniquement dans l’un des deux sous tableaux en modifiant Bi ou Bs selon que l’élément recherché est supérieur ou inférieur à V[Milieu].
Exemple :
Algorithme : TABLEAU tab[M] : ENTIER Variables D, Bi, Bs, Milieu : ENTIER Trouv : BOOLEEN DEBUT …… // remplissage du tableau v LIRE(D) Bi <-- 1 Bs <-- M Trouv <-- FAUX TANTQUE Bi <= Bs et NON Trouv Milieu <-- (Bi + Bs ) /2 Si (tab[Milieu] = D ) alors Trouv <-- VRAI SINON SI (D < tab[Milieu]) alors Bs <-- Milieu - 1 SINON Bi <-- Milieu + 1 FSI FSI FIN TANTQUE Si trouv=False alors Ecrire "n’existe pas " Sinon Ecrire "existe " FIN
Remarque: Quel est l’avantage de la recherche dichotomique?
- Dans le pire des cas d’une recherche séquentielle, il faut traverser tout le tableau avant de trouver la valeur ou avant d’être sûr qu’une valeur ne se trouve pas dans le tablea Lors de la recherche dichotomique, on élimine la moitié des éléments du tableau à chaque exécution de la boucle. Ainsi, la recherche se termine beaucoup plus rapidement.
- La recherche dichotomique devient extrêmement avantageuse pour la recherche dans de grands tableaux (triés) : L’avantage de la recherche dichotomique par rapport à la recherche séquentielle monte alors exponentiellement avec la grandeur du tableau à trier
Exercice :
Écrire un algorithme qui permet de remplir un tableau .On suppose que le tableau est ordonné de façon décroissante. On cherche une valeur dans le tableau et on affiche si elle existe ou elle n’existe pas. Pour le cas où elle existe, on affiche sa position :
- Utiliser la recherche séquentielle
- Utiliser la recherche dichotomique
Vous pouvez suivre notre liste des vidéos sur l’algorithmique sur notre chaine youtube 9raytifclick (Darija: arabe marocaine) : Cours sur les algorithmes.
Aussi, si vous voulez commencer l’apprentissage d’un langage de programmation, voilà notre cours : Langage Python Niveau 1 qui sera très utile pour vous (il vous aide à pratiquer tous les éléments vu dans notre cours d’algorithmique).