Première Occurrence par Dichotomie
Algorithmique classique
Enonce
Dans une liste triée avec doublons, trouver l'indice de la première occurrence de x par dichotomie. Retourner -1 si absent.
Signature attendue
def premiere_occurrence(L: list, x: int) -> int:Exemples
premiere_occurrence([1, 2, 2, 2, 3, 4], 2)→1premiere_occurrence([1, 1, 1, 1], 1)→0premiere_occurrence([1, 3, 5], 4)→-1
📖 Rappel de cours
Une dichotomie qui, en cas d'égalité, ne s'arrête pas : elle mémorise la position et continue à chercher à gauche, pour trouver la plus petite.
⚠ Le piège : S'arrêter au premier élément trouvé donne une occurrence quelconque, pas la première. C'est toute la différence avec la dichotomie classique.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Distance d'Édition (Levenshtein)
- Montée d'Escalier
- Recherche Dichotomique Itérative
- Recherche par Interpolation
- Recherche Ternaire du Maximum
- Point Fixe dans une Liste Triée
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.