Prépa Code Connexion Inscription

On considère un tableau trié d'entiers distincts tab. Un point fixe est un indice i tel que tab[i] == i.

Écrire une fonction point_fixe(tab) qui renvoie un indice de point fixe s'il en existe un, ou -1 sinon. La fonction doit utiliser la recherche dichotomique pour atteindre une complexité en O(log n).

Le principe est le suivant : puisque le tableau est trié et contient des entiers distincts, la fonction f(i) = tab[i] - i est croissante. On peut donc appliquer une dichotomie : - Si tab[milieu] == milieu, on a trouvé un point fixe. - Si tab[milieu] < milieu, le point fixe (s'il existe) est a droite. - Si tab[milieu] > milieu, le point fixe (s'il existe) est a gauche.