Point fixe

Les valeurs sont des entiers distincts et croissants : $T[i+1]\ge T[i]+1$. La suite $T[i]-i$ est donc croissante au sens large, et l'on cherche un zéro de cette suite : c'est une dichotomie.

static int pointFixe(int[] T) {
    int g = 0, d = T.length;
    // I(g,d) : T[i] < i pour i dans [0:g], T[i] > i pour i dans [d:n]
    while (g < d) {
        int m = g + (d - g) / 2;
        if (T[m] == m) return m;
        if (T[m] < m) g = m + 1;     // T[i] - i <= T[m] - m < 0 pour i <= m
        else d = m;                  // T[i] - i >= T[m] - m > 0 pour i >= m
    }
    return -1;                       // [g:d] vide : aucun point fixe
}

13.8 : 3 -1 0

(pour $[-4,-1,1,3,7,9]$, $[-3,0,1,2,5]$ et $[0,2,5]$.)

nom : T
valeurs : -4 -1 1 3 7 9
vert : 3
pointeurs : g=0 m=3 d=6
zone : 0..2 T[i] < i
zone : 4..5 T[i] > i
legende : T[i] - i croît : -4, -2, -1, 0, 3, 4 ; m = 3 est un point fixe

Sans l'hypothèse « distincts », la suite $T[i]-i$ n'est plus monotone et la dichotomie ne marche plus : pour $[-1,2,2,2,2]$, elle vaut $-1,1,0,-1,-2$.