Recherche d’un élément dans un tableau
La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :
- La recherche linéaire itérative ;
- La recherche linéaire récursive ;
- La recherche dichotomique itérative ;
- La recherche dichotomique récursive.
Travail à faire
- Implémenter en Python les cinq algorithmes suivants et répondre aux questions.
Penser à donner la spécification de chacune des fonctions et écrire une série des tests pour chacune d’elles.
Recherche séquentielle (ou linéaire)
La recherche séquentielle (ou linéaire) consiste à
comparer la valeur recherchée à toutes les valeurs présentes dans le tableau.
Recherche séquentielle itérative
Algorithme 1
Fonction : recherche(tab, valeur)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début
i ⟵ 0
i_val ⟵ -1
nb ⟵ Longueur(tab)
TantQue i < nb Faire
Si tab[i] = valeur Alors
i_val ⟵ i
FinSi
i ⟵ i + 1
FinTantQue
Renvoyer i_val
Fin