Première · Numérique et sciences informatiques
Découvrir parcours, recherche et tri : trois familles d'algorithmes sur les tableaux
Distinguer parcours, recherche (linéaire et dichotomique) et tri par insertion sur un tableau, savoir dire ce que fait chacun et dans quel cas l'utiliser, puis le dérouler à la main sur un petit exemple.
Aperçu gratuit

Les points essentiels
- Un parcours consiste à visiter les éléments d'un tableau un par un, en général avec une boucle for sur les indices ou sur les valeurs ; c'est la brique de base de presque tous les algorithmes de ce chapitre.
- La recherche linéaire (séquentielle) parcourt le tableau du début à la fin et compare chaque élément à la valeur cherchée ; elle fonctionne sur un tableau trié ou non, et dans le pire cas elle effectue autant de comparaisons que d'éléments.
Les mots à connaître
- Parcours séquentiel
- Visite de tous les éléments d'un tableau dans l'ordre des indices 0, 1, ..., len(t)-1, par exemple avec for i in range(len(t)) ou for x in t.
- Recherche dichotomique
- Méthode de recherche dans un tableau trié qui divise à chaque étape par deux la zone de recherche en comparant la valeur cherchée à l'élément central.
Un exemple pour comprendre
On cherche la valeur 9 dans t = [4, 7, 2, 9, 5]. Déroule la recherche linéaire en donnant l'indice renvoyé et le nombre de comparaisons.
On parcourt dans l'ordre : i=0, t[0]=4 différent de 9 ; i=1, t[1]=7 différent de 9 ; i=2, t[2]=2 différent de 9 ; i=3, t[3]=9 égal à 9, on s'arrête. L'indice renvoyé est 3 et on a fait 4 comparaisons. Si la valeur cherchée avait été 8, on aurait parcouru les 5 éléments sans succès (5 comparaisons) et renvoyé -1 ou False. Le tableau n'étant pas trié, la dichotomie ne serait pas applicable ici.

