Algorithmes de recherche : parcourir un tableau
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- 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 |
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
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 à
