La dichotomie qui boucle — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

La dichotomie qui boucle

Recherche séquentielle, dichotomique, arrière · niveau 1 (application)

Énoncé

Un étudiant a écrit la recherche suivante.


static int recherche(int[] T, int x) {
    int g = 0, d = T.length;
    while (g < d) {
        int m = (g + d) / 2;
        if (T[m] < x) g = m;
        else d = m;
    }
    return g;
}

Exécuter recherche(S, 3) avec $S = [1, 3, 3, 3, 6, 8, 11, 15]$ . Que se passe-t-il ?
Pour quelles valeurs de $x$ la fonction termine-t-elle ?
Corriger la fonction en partant de l'invariant « $T [0 : g] < x$ et $T [d : n] \geq x$ ».

Corrigé

Pour $x = 3$ : $(g, d) = (0, 8)$ , $m = 4$ , $T [4] = 6 \geq 3$ donc $d = 4$ ; puis $m = 2$ , $d = 2$ ; puis $m = 1$ , $d = 1$ ; puis $m = 0$ , $T [0] = 1 < 3$ donc $g = 0$ … et $(g, d) = (0, 1)$ ne change plus. La fonction ne termine pas.


nom : S
valeurs : 1 3 3 3 6 8 11 15
griser : 1..7
colorier : 0
pointeurs : g=0 m=0 d=1
legende : T[0] = 1 < 3 : g = m = 0, rien ne change et la boucle tourne

Le défaut apparaît dès que $d = g + 1$ et $T [g] < x$ : alors $m = g$ et l'affectation $g = m$ ne change rien. La fonction termine seulement si cette situation n'arrive jamais, c'est-à-dire si l'on n'avance jamais $g$ : pour $x \leq T [0]$ . Le programme le confirme (on coupe la boucle au bout de $100$ tours et on retourne $- 999$ ) :


fausse(S, 3) = -999
fausse(S, 0) = 0
fausse(S, 7) = -999

Avec l'invariant « $T [0 : g] < x$ et $T [d : n] \geq x$ », si $T [m] < x$ alors $T [0 : m + 1] < x$ : il faut écrire g = m + 1. On retrouve exactement premierIndice, dont la zone $[g : d]$ diminue strictement à chaque tour.