Algorithmes de recherche en tableaux
Transféré par
Mohamed SaidiAlgorithmes de recherche en tableaux
Transféré par
Mohamed SaidiLycée Pilote de Sousse 2011/2012
Les algorithmes de recherches
Recherche Séquentielle
La méthode de recherche séquentielle d’un élément dans un tableau consiste à parcourir le
tableau élément par élément en les comparant avec l’élément à chercher jusqu’à trouver ce
dernier ou achever le tableau.
DEF FN recherche_s (…,…… :entier ; … :tab) : ……………………
Résultat = recherche_s exist
………….. = [] Si (……… = m) alors
…………. vrai T.D.O Locaux
sinon Rôle Type Objet
…………. ……….. compteur ……… ………
FinSi Indique l’existance de l’élément ..… ………
recherché dans le tableau ……… …
i = […………..] répéter .……
….. ……………
jusqu'à (………….) ou (……………)
Fin recherche_s
Recherche dichotomique
On vérifie l’élément au milieu du tableau.
S’il st égale à la valeur recherchée, l’élément cherché est existant.
S’il est inférieur à la valeur cherchée, il ne reste à traiter que la moitié droite du
tableau.
S’il est supérieur à la valeur recherchée, il ne reste à traiter que la moitié gauche du
tableau.
On continu ainsi la recherche en diminuant à chaque fois de moitié le nombre
d’éléments du tableau restant à traiter.
On répète cette opération jusqu'à ce qu’on trouve l’élément recherché ou la position
de début du tableau dépasse la position de fin
DEF FN recherche_d (…. :tab ; …..,….. :……………..) :…………………….
Résultat = recherche_d ………………..
trouve = [……………….. 1, ………………. n, …………………faux]
Répéter
………………. (……………..+……………..) DIV 2
Si (……..=t[……………..]) Alors
………………..…………………..
Sinon Si (m<t[…………………..]) Alors
………………… …………………….
Sinon
Debut …………………………..
FinSi
jusqu'à (…………………) ou (………………..>…………………….)
Fin Recherche_d
T.D.O Locaux
Rôle Type Objet
Position de debut pendant la recherche .…………… ……………
Position de fin pendant la recherche . .…
Milieu du tableau .…………… ……………
Indique l’existance de l’élément recherché dans le tableau . ..
…………… ……………
Page |1
Lycée Pilote de Sousse 2011/2012
… ..…
…………… ……………
…… ..
Traduction Pascal :
Recherche Séquentielle Recherche dichotomique
Page |2
Lycée Pilote de Sousse 2011/2012
Page |3
