Première · Numérique et sciences informatiques

Comprendre la recherche séquentielle (linéaire) dans un tableau

Décrire, dérouler à la main et justifier une recherche séquentielle dans un tableau Python, puis en déterminer le coût (nombre de comparaisons) dans le meilleur cas, le pire cas et le cas d'absence.

Aperçu gratuit
Illustration de la fiche « Comprendre la recherche séquentielle (linéaire) dans un tableau »

Les points essentiels

  • La recherche séquentielle (ou linéaire) consiste à examiner les cases d'un tableau une par une, de l'indice 0 vers la fin, jusqu'à trouver la valeur cherchée ou épuiser toutes les cases.
  • Elle ne demande aucune hypothèse sur le tableau : il n'a pas besoin d'être trié, ce qui la distingue de la recherche dichotomique qui exige un tableau trié.

Les mots à connaître

Recherche séquentielle (linéaire)
Algorithme qui examine les éléments d'un tableau dans l'ordre des indices, un par un, jusqu'à trouver l'élément cherché ou atteindre la fin du tableau.
Invariant de boucle
Propriété vraie avant la première itération et conservée après chaque itération ; ici : « aucune des cases d'indice inférieur à i ne contient la valeur cherchée ».

Un exemple pour comprendre

On considère le tableau t = [12, 7, 9, 7, 20] et la fonction suivante. def cherche(t, v): for i in range(len(t)): if t[i] == v: return i return -1 Donner le résultat de cherche(t, 7) et de cherche(t, 15), avec le nombre de comparaisons dans chaque cas.

Pour v = 7 : i = 0, t[0] = 12 ≠ 7 (1 comparaison) ; i = 1, t[1] = 7 = 7 (2e comparaison), donc return 1. Le résultat est 1, obtenu en 2 comparaisons. La seconde occurrence de 7 (indice 3) n'est jamais examinée car le return interrompt la boucle. Pour v = 15 : on compare avec 12, 7, 9, 7 et 20, aucune égalité, soit 5 comparaisons, la boucle se termine et la fonction renvoie -1.

Première page de l’Essentiel : Comprendre la recherche séquentielle (linéaire) dans un tableau
Ketty