Accueil › Cours › La recherche dans un tableau

Les leçons de ce chapitre

1. La recherche séquentielle
2. La recherche dichotomique
3. Compter et lister les occurrences

Leçon 15.1 : La recherche séquentielle

9 min

La recherche séquentielle regarde les cases une par une, depuis le début, jusqu'à trouver la valeur cherchée ou arriver à la fin du tableau. Elle marche sur n'importe quel tableau, trié ou pas.

• On avance tant qu'on n'est pas au bout et que la case n'est pas la bonne : Tant que (i ≤ n) et (T[i] ≠ x).
• Après la boucle, si i ≤ n, la valeur est trouvée à la position i. Sinon elle n'existe pas.

Attention : L'ordre des deux tests compte : on vérifie i ≤ n avant de lire T[i], sinon on lit une case qui n'existe pas.

Astuce : Avec Tant que, la boucle s'arrête d'elle-même dès qu'on trouve : pas besoin de break en Python.

En Python

En Python la première case est 0 : on affiche le rang i + 1 pour parler comme en classe (1er, 2e…).

t = [12, 7, 19, 4, 7]
n = len(t)
x = int(input())
i = 0
while i < n and t[i] != x:
    i = i + 1
if i < n:
    print("Trouvé au rang", i + 1)
else:
    print("Introuvable")

En algorithme

En algorithme, les cases vont de 1 à n : le rang est directement i.

Algorithme RechercheSeq
Début
  T[1] ← 12
  T[2] ← 7
  T[3] ← 19
  T[4] ← 4
  T[5] ← 7
  n ← 5
  Lire(x)
  i ← 1
  Tant que (i ≤ n) et (T[i] ≠ x) Faire
    i ← i + 1
  FinTantQue
  Si i ≤ n Alors
    Ecrire("Trouvé au rang ", i)
  Sinon
    Ecrire("Introuvable")
  FinSi
Fin

TDO
Objet | Type/Nature
T | Tableau de 5 Entiers
n, x, i | Entier

Leçon 15.2 : La recherche dichotomique

11 min

Quand le tableau est trié, on peut chercher beaucoup plus vite. La recherche dichotomique regarde la case du milieu : si c'est la bonne valeur, on a fini ; si la valeur cherchée est plus petite, on garde la moitié gauche ; sinon la moitié droite. À chaque tour, la zone de recherche est coupée en deux.

• Deux bornes : inf (début de la zone) et sup (fin de la zone).
• Le milieu : m ← (inf + sup) div 2.
• Si x < T[m] alors sup ← m - 1, sinon inf ← m + 1.
• On s'arrête quand on a trouvé, ou quand inf > sup (zone vide).

Attention : La recherche dichotomique ne marche que sur un tableau trié. Sur un tableau en désordre, elle peut répondre « introuvable » alors que la valeur existe.

Astuce : Pour 1000 cases triées, la recherche séquentielle peut faire 1000 comparaisons ; la dichotomique en fait au plus 10.

En Python

Le tableau est trié. La variable trouve arrête la boucle sans break.

t = [3, 8, 11, 15, 20, 26, 31]
x = int(input())
inf = 0
sup = len(t) - 1
trouve = False
while inf <= sup and not trouve:
    m = (inf + sup) // 2
    if t[m] == x:
        trouve = True
    elif x < t[m]:
        sup = m - 1
    else:
        inf = m + 1
if trouve:
    print(x, "existe")
else:
    print(x, "n'existe pas")

En algorithme

Même algorithme avec les cases 1 à 7.

Algorithme Dichotomie
Début
  T[1] ← 3
  T[2] ← 8
  T[3] ← 11
  T[4] ← 15
  T[5] ← 20
  T[6] ← 26
  T[7] ← 31
  Lire(x)
  inf ← 1
  sup ← 7
  trouve ← Faux
  Tant que (inf ≤ sup) et (Non trouve) Faire
    m ← (inf + sup) div 2
    Si T[m] = x Alors
      trouve ← Vrai
    Sinon Si x < T[m] Alors
      sup ← m - 1
    Sinon
      inf ← m + 1
    FinSi
  FinTantQue
  Si trouve Alors
    Ecrire(x, " existe")
  Sinon
    Ecrire(x, " n'existe pas")
  FinSi
Fin

TDO
Objet | Type/Nature
T | Tableau de 7 Entiers
x, inf, sup, m | Entier
trouve | Booléen

Leçon 15.3 : Compter et lister les occurrences

8 min

Parfois on ne s'arrête pas à la première trouvaille : on veut savoir combien de fois une valeur apparaît (sa fréquence, ou son nombre d'occurrences), ou toutes ses positions. On parcourt alors tout le tableau avec une boucle Pour.

• Fréquence : un compteur nb ← 0, augmenté à chaque case égale à x.
• Positions : on affiche i à chaque case égale à x.

Astuce : Choisis la boucle selon la question : Tant que pour « existe-t-il ? » (on peut s'arrêter tôt), Pour pour « combien ? » (il faut tout voir).

En Python

On compte les notes égales à la note lue.

notes = [12, 15, 12, 9, 12, 15]
x = int(input())
nb = 0
for i in range(len(notes)):
    if notes[i] == x:
        nb = nb + 1
print("La note", x, "apparaît", nb, "fois")

En algorithme

Une boucle Pour sur les 6 cases, un compteur.

Algorithme Frequence
Début
  T[1] ← 12
  T[2] ← 15
  T[3] ← 12
  T[4] ← 9
  T[5] ← 12
  T[6] ← 15
  Lire(x)
  nb ← 0
  Pour i de 1 à 6 Faire
    Si T[i] = x Alors
      nb ← nb + 1
    FinSi
  FinPour
  Ecrire("La note ", x, " apparaît ", nb, " fois")
Fin

TDO
Objet | Type/Nature
T | Tableau de 6 Entiers
x, nb, i | Entier

S'entraîner gratuitement

Chaque leçon a 3 exercices gratuits avec indices pour appliquer ce chapitre avec Hannibot.

← Chapitre précédent : Les tris · Chapitre suivant : Arithmétique →

Tous les chapitres · Voir les devoirs corrigés de 2ème TI

Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.