Recherche Dichotomique Itérative
Algorithmique classique
Enonce
Rechercher l'indice de x dans une liste triée L par dichotomie itérative. Retourner -1 si absent.
Signature attendue
def recherche_dicho(L: list, x: int) -> int:Exemples
recherche_dicho([1, 3, 5, 7, 9, 11], 7)→3recherche_dicho([1, 3, 5, 7, 9, 11], 4)→-1recherche_dicho([2, 4, 6], 2)→0
📖 Rappel de cours
On compare à l'élément du milieu et on élimine la moitié qui ne peut pas contenir la valeur. On répète tant que l'intervalle n'est pas vide.
⚠ Le piège : La liste doit être triée, sinon l'algorithme n'a aucun sens. Et le calcul du milieu doit utiliser // : un indice flottant lève une erreur.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Plus Longue Sous-séquence Commune (LCS)
- Distance d'Édition (Levenshtein)
- Montée d'Escalier
- Première Occurrence par Dichotomie
- Recherche par Interpolation
- Recherche Ternaire du Maximum
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.