module · recherche dichotomique · 8 min
À chaque étape, l'intervalle de recherche est divisé par deux.
Vous savez que le tableau est trié. À vous de jouer : à chaque tour, cliquez sur l'élément au milieu de la plage encore en course. Combien de comparaisons faut-il, par rapport à un balayage linéaire ?
défi · tenir le budget
palier 1 / 4
Trouver la cible dans le tableau sans dépasser le budget de comparaisons. Chaque clic compte, même un mauvais.
≤ ⌈log₂(n+1)⌉cible28
budget restant
3 / 3
intervalle actif : [0, 6] · milieu : 3
comparaisons : 0 · borne ⌈log₂(n+1)⌉ = 3 · n = 7
bac à sable · explore librement
Sans budget ni objectif : générez des parties, cliquez où vous voulez, comparez la dichotomie au balayage linéaire.
cible
0tableau trié — cliquez pour comparer
intervalle actif : [0, 0] · milieu suggéré : 0vos comparaisons (dichotomie)
0
optimal : ⌈log₂(n+1)⌉ = 0
recherche linéaire (équivalent)
0
dans le pire des cas : n = 0
gain de la dichotomie
×—
plus rapide que linéaire ici
24
à retenir
- La dichotomie ne fonctionne que si le tableau est trié.
- À chaque étape, on compare la cible à l'élément du milieu : égal, plus petit, plus grand.
- La taille de l'intervalle est divisée par 2 à chaque tour : complexité O(log n).
- Pour 1 million d'éléments : la dichotomie demande au plus 20 comparaisons, la recherche linéaire jusqu'à 1 000 000.