Recherche Dichotomique
Diviser pour mieux chercher
Enonce
Soit T une liste d'entiers triée croissante. Retourner l'indice de x dans T, ou -1 si absent.
⚠ Contrainte : Complexité $O(\log n)$ obligatoire.
Signature attendue
def recherche_dicho(T: list, x: int) -> int:Exemples
recherche_dicho([1,3,5,7,9,11,15,21,34,55], 11)→5recherche_dicho([1,3,5,7,9,11,15,21,34,55], 4)→-1
📖 Rappel de cours
La recherche dichotomique s'applique à une liste triée. À chaque étape, on compare l'élément cherché à l'élément médian et on élimine la moitié du tableau restant.
Invariant :
Si $x$ est dans le tableau, alors $x \in T[g..d]$
Complexité :
$T(n) = T(n/2) + O(1) \Longrightarrow T(n) = O(\log n)$
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.