Recherche dans un tableau : recherche séquentielle et recherche dichotomique

En 30 secondes

• Recherche séquentielle : examine les éléments un par un, fonctionne sur tout tableau, trié ou non.
• Recherche dichotomique : compare à l'élément du milieu et élimine une moitié à chaque étape, mais exige un tableau trié.
• Indice du milieu = (borne inférieure + borne supérieure) ÷ 2, arrondi à la partie entière.

Ce que tu sauras faire

• Distinguer recherche séquentielle et recherche dichotomique, et savoir quand utiliser chacune.
• Dérouler à la main une recherche séquentielle dans un tableau.
• Dérouler à la main une recherche dichotomique dans un tableau trié, en calculant l'indice du milieu à chaque étape.

Les mots à connaître

Tableau

une structure de données qui stocke une suite de valeurs, chacune repérée par son indice (sa position).

Indice

la position d'un élément dans un tableau, en commençant à 0 pour le premier élément.

Tableau trié

un tableau dont les éléments sont rangés par ordre croissant (ou décroissant).

Le piège classique

Appliquer une recherche dichotomique sur un tableau NON trié : le résultat n'est pas garanti, la méthode suppose un tableau trié.

L'astuce

Recherche séquentielle = tableau trié ou non, mais lente sur un grand tableau. Recherche dichotomique = tableau OBLIGATOIREMENT trié, mais beaucoup plus rapide.