Dérouler une dichotomie

• Avec $x=3$, le programme Dichotomies.java affiche :

g=0 d=8 m=4 T[m]=6
g=0 d=4 m=2 T[m]=3
g=0 d=2 m=1 T[m]=3
g=0 d=1 m=0 T[m]=1
fin : g=d=1

Chaque fois que $T[m]\ge 3$, on pose $d=m$ ; seule la dernière comparaison ($T[0]=1<3$) fait avancer $g$. La fonction retourne $1$ : c'est la première occurrence de $3$.

• Avec $x=7$ :

g=0 d=8 m=4 T[m]=6
g=5 d=8 m=6 T[m]=11
g=5 d=6 m=5 T[m]=8
fin : g=d=5

La fonction retourne $5$ : c'est la position d'insertion de $7$, l'indice de la première valeur supérieure ou égale à $7$ ($T[5]=8$). On en déduit que $7$ n'est pas dans $S$, puisque $T[5]\ne 7$.

nom : S
valeurs : 1 3 3 3 6 8 11 15
griser : 0..4
colorier : 6
pointeurs : g=5 m=6 d=8
legende : x = 7, tour 2 : T[4] = 6 < 7 a écarté T[0:5]

nom : S
valeurs : 1 3 3 3 6 8 11 15
griser : 0..4 6..7
colorier : 5
pointeurs : g=5 m=5 d=6
legende : x = 7, tour 3 : T[6] = 11 ≥ 7 a écarté T[6:8]

• Pour $x=3$, $g=d=1$ : $S[0:1]=[1]<3$ et $S[1:8]\ge 3$. Pour $x=7$, $g=d=5$ : $S[0:5]=[1,3,3,3,6]<7$ et $S[5:8]=[8,11,15]\ge 7$. Dans les deux cas l'invariant est vrai et la zone d'incertitude $[g:d]$ est vide.

nom : S
valeurs : 1 3 3 3 6 8 11 15
pointeurs : g=5 d=5
zone : 0..4 < 7
zone : 5..7 au moins 7
legende : x = 7 : g = d = 5, la zone d'incertitude est vide

Il y a eu $4$ puis $3$ tours de boucle, soit au plus $\lceil {\log }_{2}9\rceil =4$ : la zone $[g:d]$ est au moins divisée par deux à chaque tour.