Animation de la recherche séquentielle
Cette page présente une animation permettant de comprendre le principe de la recherche sequentielle.
L'algorithme de recherche est sous l'animation.
1 - Animation
On notera que le tableau n'a pas besoin d'être trié.
Recherche séquentielle d'une valeur
Valeur cherchée :
| Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
| Elément | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 | |
Recherche séquentielle de la valeur maximale
| Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Elément | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 |
2 - Algorithmes
On y présente l'algorithme de recherche de valeur puis l'algorithme de recherche du maximum.
Algorithme de recherche séquentielle
But : trouver si un élément recherché existe bien dans un tableau. S'il existe, on fournit l'index de la première occurrence trouvée. Sinon, il renvoie une réponse vide.
Principe : lecture séquentielle et progressive des différents éléments. On renvoie l'index du premier élément qui correspond. VIDE si aucun des éléments n'a correspondu à la recherche.
Description des entrées / sortie
ENTREES:tableau: un tableau contenant un ensemble d'éléments.x: un élément voulu qu'on tente de rechercher dans le tableau- (optionnelle selon les langages d'implémentation):
longueur, le nombre d'éléments dans le tableau SORTIE: une réponse vide (à définir) ou un nombre correspondant à l'index trouvé.
Exemple :
Prenons tableau = [13, 18, 89, 1024, 45, -12, 18]
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Elément | 13 | 18 | 89 | 1024 | 45 | -12 | 18 |
L'application de l'algorithme de recherche
- sur l'élément 89 doit renvoyer 2 (présence à l'index 2).
- sur l'élément 18 doit renvoyer 1 (présence sur l'index 1 et 6)
- sur l'élement 105 doit renvoyer une valeur signifiant vide (prenons None comme en Python par exemple, ou -1 pour indiquer qu'il s'agit d'une absence d'index).
La valeur exacte de VIDE doit être gérée au moment de l'implémentation dans un langage.
Description de l'algorithme
index ← 0
TANT QUE index < longueur et que tableau[index] est différent de x
index ← index + 1
Fin TANT QUE
SI index < longueur
Renvoyer index
Fin Si
Renvoyer VIDE
Algorithme de recherche de maximum
Principe
On place le premier élément du tableau en tant que valeur maximale. Ensuite, on compare chaque élément lu séquentiellememt à ce maximum : on remplace le maximum si l'élément lu est plus grand.
Description des entrées / sortie
ENTREES:tableau: un tableau d'au moins un élément.- (optionnelle selon les langages d'implémentation):
longueur, le nombre d'éléments dans le tableau SORTIE: la valeur maximale.
Description de l'algorithme
maxi ← tableau[0]
index ← 1
TANT QUE index < longueur
SI tableau[index] > maxi
maxi ← tableau[index]
index ← index + 1
Fin du SI
Fin du TANT QUE
Renvoyer maxi
3 - Python
Recherche séquentielle d'une valeur dans un tableau
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | def trouverIndex(tableau, x):
'''Fonction qui renvoie l'index de l'élément x dans le tableau. None en cas d'échec de la recherche
:: param tableau(list) :: un tableau contenant le même type d'élément que le paramètre x
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau
:: exemples ::
>>> test = [10,20,30,40,50]
>>> trouverIndex(test, 20)
1
>>> trouverIndex(test, 60)
'''
index = 0
longueur = len(tableau)
while index < longueur and tableau[index] != x :
index = index + 1
if index < longueur :
return index
return None # Inutile en réalité : ce serait fait automatiquement
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Recherche d'une valeur dans un dictionnaire (avec la méthode keys)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | def trouverCle(dictionnaire, x):
'''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche
:: param dictionnaire(dict) :: un dictionnaire
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire
:: return (comme les clés) :: la clé correspondant à la valeur x
:: exemples ::
>>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'}
>>> trouverCle(test, 'data')
'données'
>>> trouverCle(test, 'stack')
'''
for cle in dictionnaire.keys():
if dictionnaire[cle] == x :
return cle
return None # Inutile en réalité : ce serait fait automatiquement
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Recherche d'une valeur dans un dictionnaire (avec la méthode items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | def trouverCle(dictionnaire, x):
'''Fonction qui renvoie la première clé associée à la valeur x dans le dictionnaire. None en cas d'échec de la recherche
:: param dictionnaire(dict) :: un dictionnaire
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le dictionnaire
:: return (comme les clés) :: la clé correspondant à la valeur x
:: exemples ::
>>> test = {'boucle':'loop', 'données':'data', 'tant que':'while'}
>>> trouverCle(test, 'data')
'données'
>>> trouverCle(test, 'stack')
'''
for (cle, valeur) in dictionnaire.items():
if valeur == x :
return cle
return None # Inutile en réalité : ce serait fait automatiquement
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Recherche du maximum dans un tableau
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | def trouverMax(tableau):
'''Fonction qui renvoie la valeur maximale lue dans le tableau
:: param tableau(list) :: un tableau d'éléments qu'on peut comparer
:: return (type en fonction du tableau) :: la valeur maximale
:: exemples ::
>>> test = [10,20,60,40,50]
>>> trouverMax(test)
60
>>> test = [10,20,60,40,50,100]
>>> trouverMax(test)
100
>>> test = [100,20,60,40,50]
>>> trouverMax(test)
100
'''
maxi = tableau[0]
for index in range( 1, len(tableau) ):
if tableau[index] > maxi :
maxi = tableau[index]
return maxi
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Recherche du minimum dans un tableau
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | def trouverMin(tableau):
'''Fonction qui renvoie la valeur minimale lue dans le tableau
:: param tableau(list) :: un tableau d'éléments qu'on peut comparer
:: return (type en fonction du tableau) :: la valeur maximale
:: exemples ::
>>> test = [10,20,60,40,50]
>>> trouverMin(test)
10
>>> test = [10,20,60,40,50,100]
>>> trouverMin(test)
10
>>> test = [100,20,60,40,50]
>>> trouverMin(test)
20
'''
mini = tableau[0]
for index in range( 1, len(tableau) ):
if tableau[index] < mini :
mini = tableau[index]
return mini
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Recherche de la moyenne dans un tableau
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | def trouverMoy(tableau):
'''Fonction qui renvoie la valeur moyenne des valeurs du tableau
:: param tableau(list) :: un tableau NON VIDE d'entiers ou de flottants
:: return (float) :: la valeur moyenne
:: exemples ::
>>> test = [10,20,60,40,50]
>>> trouverMoy(test)
36.0
>>> test = [100,20,60,40,50]
>>> trouverMoy(test)
54.0
'''
somme = 0
longueur = len(tableau)
for index in range(longueur):
somme = somme + tableau[index]
return somme / longueur
if __name__ == '__main__' :
import doctest
doctest.testmod()
|
Article publié le 11 04 2020
Dernière modification : 13 04 2020
Auteur : ows. h.