Algorithmes de recherche : parcourir un tableau
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
- Utiliser une instruction for pour parcourir un tableau.
- Écrire un algorithme de recherche d’un élément dans un tableau.
- Le cout d’un algorithme caractérise l’efficacité de celui-ci. En NSI, il correspond à son temps d’exécution.
- Le cout d’une recherche dans un tableau est linéaire en n la taille du tableau.
- Le langage Python permet d’utiliser l’instruction for appliquée aux tableaux de deux manières différentes : à partir des indices avec range() et len() ou en contrôle de flux.
- Manipuler les tableaux
- Définir une fonction
- Utiliser une instruction conditionnelle
Voici ci-dessous un algorithme classique de recherche d’un élément b dans un tableau Tab (non vide et non trié) de taille n. Cet algorithme affecte le booléen Vrai à la variable trouve si b est un élément de Tab et affecte Faux sinon.
| trouve ← Faux | Faux est affecté à la variable trouve |
| Pour i allant de 0 à n-1 | i = 0, puis i = 1, puis i = 2, puis… i = n − 1 |
| Si b = Tab[i], alors | Si Tab[i] est égal à b, alors |
| trouve ← Vrai | on affecte Vrai à la variable trouve |
| FinSi | Fin de l’instruction « Si » |
| FinPour | Fin de l’instruction « Pour » |
i prend des valeurs de 0 à n − 1 car, en informatique, les tableaux sont généralement indexés à partir de 0.
- Une affectation est une procédure qui permet d’attribuer une valeur à une variable.
- Une comparaison est une instruction qui met en jeu deux variables et qui renvoie True ou False (Vrai ou Faux).
L’algorithme de la sous-partie précédente, appliqué à un tableau comportant n éléments, nécessite :
- n + 1 affectations : une affectation avant l’instruction for, et n affectations pendant celle-ci ;
- n comparaisons : dans l’instruction pour.
(car a × (n + 1) + c × n = an + a + cn).
On obtient une fonction affine en n. On dit alors que le cout d’une recherche dans un tableau est linéaire en n la taille du tableau.
Le cout d’une recherche dans un tableau non trié est linéaire.
On implémente un algorithme de recherche en Python de deux manières différentes : à partir des indices avec range() et len() ou en contrôle de flux.
Pour écrire un script de recherche d’un élément dans un tableau, on peut utiliser les instructions avec range() et len().
- L’instruction len(Tab) renvoie la longueur
du tableau Tab, c’est-à-dire
son nombre d’éléments.
Exemple
Si Tab = [1,2,5,7], alors len(Tab) retournera 4. - L’instruction for i in range(n) affecte successivement à la variable i tous les entiers de 0 à n − 1.
En Python, la fonction recherche1(Tab, b) implémente un algorithme de recherche de b dans Tab : elle retourne True si b est un élément de Tab et False sinon.
| def recherche1(Tab, b): | On définit la fonction recherche1 |
| trouve = False | Faux est affecté à la variable trouve |
| for i in range(len(Tab)): | i = 0, puis i = 1, puis i = 2, puis… i = n − 1 |
| if b == Tab[i]: | Si Tab[i] est égal à b, alors |
| trouve = True | on affecte Vrai à la variable trouve |
| return trouve |
On retourne la variable trouve
|
Pour parcourir un tableau en contrôle de flux, on utilise l’instruction for elt in Tab.
L’instruction for elt in Tab permet d’affecter successivement à la variable elt chaque élément du tableau Tab.
Si Tab=[1, 2, 5, 7], for elt in Tab signifie que que elt prend successivement les valeurs 1, 2, 5 et 7.
En Python, la fonction recherche2 suivante implémente l’algorithme de recherche de b dans Tab.
| def recherche2(Tab, b): | On définit la fonction recherche2 |
| trouve = False | Faux est affecté à la variable trouve |
| for elt in Tab: | elt prend les valeurs de Tab |
| if b == elt: | Si elt est égal à b, alors |
| trouve = True | on affecte Vrai à la variable trouve |
| return trouve | On retourne la variable trouve |
Comment as-tu trouvé ce cours ?
Évalue ce cours !
Vous avez obtenu75%de bonnes réponses !
Recevez l'intégralité des bonnes réponses ainsi que les rappels de cours associés :
Fiches de cours les plus recherchées
NSI
Algorithmes de recherche : rechercher un extremum
NSI
Algorithmes de recherche : obtenir une moyenne, une médiane
NSI
Trier par insertion
NSI
Trier par sélection
NSI
Utiliser les invariants pour corriger un algorithme
NSI
Comprendre et utiliser l'algorithme des k plus proches voisins
NSI
L'algorithme de recherche dichotomique dans un tableau trié
NSI
Résoudre un problème avec un algorithme glouton
NSI
Écrire un entier positif dans une base donnée
NSI
Passer de la représentation d'une base à une autre
NSI
Comprendre les bases de la représentation binaire
NSI
Effectuer des opérations en binaire
NSI
Utiliser la méthode du complément à 2 en binaire
NSI
Représenter les nombres réels en binaire
NSI
Comprendre les booléens
NSI
Utiliser les opérateurs booléens élémentaires
NSI
Obtenir une table de vérité d'une expression booléenne complexe
NSI
Représenter un texte en utilisant différents encodages
Fermer
Accédez gratuitement à
