Point Fixe dans une Liste Triée
Algorithmique classique
Enonce
Dans une liste triée d'entiers distincts, trouver un indice i tel que L[i] == i par dichotomie. Retourner -1 si aucun point fixe n'existe.
Signature attendue
def point_fixe(L: list) -> int:Exemples
point_fixe([-1, 0, 2, 4, 7])→2point_fixe([0, 1, 2, 3])→0 (ou 1, 2, 3)point_fixe([1, 2, 3, 4])→-1
📖 Rappel de cours
On cherche un indice tel que L[i] == i. Sur une liste triée d'entiers distincts, la dichotomie s'applique : si l’élément du milieu est inférieur à son propre indice, le point fixe ne peut être qu’à droite.
⚠ Le piège : Ce raisonnement exige des entiers strictement croissants. Avec des doublons, la propriété tombe et il faut parcourir.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Première Occurrence par Dichotomie
- Recherche par Interpolation
- Recherche Ternaire du Maximum
- Liste Chaînée — Création et Affichage
- Inversion d'une Liste Chaînée
- Détection de Cycle (Floyd)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.