Comparer les recherches - Recherche NSI

Tableau comparatif

synthèse

Les deux méthodes résolvent le même problème mais avec des hypothèses différentes.

Précondition séquentielle

Aucune (tri non requis)

Précondition dichotomie

Tableau trié

Pire cas séquentielle

O(n)

Pire cas dichotomie

O(log n)

Simplicité

Séquentielle plus simple ; dichotomie plus technique

Critère	Recherche séquentielle	Recherche dichotomique
Tableau trié requis	Non	Oui
Complexité pire cas	O(n)	O(log n)
Meilleur cas	O(1) (1^er élément)	O(1) (milieu exact)
Facilité de programmation	Très facile	Moyenne (indices, boucle)
Liste chaînée	Adapté	Peu adapté
Grand n, nombreuses recherches	Lent	Très efficace si déjà trié
Petit n, tableau non trié	Recommandé	Inutile (tri coûteux)

Séquentielle : données non triées, petit effectif, une seule recherche, structure sans accès direct au milieu.
Dichotomie : tableau trié (ou tri une fois), grandes tailles, plusieurs recherches sur les mêmes données.
Rappel : trier puis chercher en dichotomie coûte O(n log n) + O(log n) ; une seule recherche sur données non triées → rester en séquentielle.

Pour n = 1 000 000 éléments (pire cas, nombre de comparaisons ≈) :

Méthode Comparaisons (ordre de grandeur)

Séquentielle jusqu'à 1 000 000

Dichotomie environ 20 (log₂(1 000 000) ≈ 20)

La dichotomie effectue environ 50 000 fois moins de tests dans ce scénario : d'où l'intérêt du tri + dichotomie quand on cherche souvent.

« Déterminer la complexité en O du pire cas » : compter la boucle dominante ou le nombre de divisions par 2.

« Justifier le choix de l'algorithme » : lier tri / non tri, taille de n, nombre de recherches.