Recherche dichotomique contre recherche linéaire

Dichotomie, pire cas

20 étapes

Recherche linéaire, pire cas

1 000 000 étapes

Recherche linéaire, cas moyen

500 001 étapes

Gain au pire cas

× 50 000

La dichotomie suppose une liste déjà triée.