Recherche dichotomique☘
La fonction recherche ci-dessous prend en paramètres:
- un tableau tab d'entiers (non vide) trié dans l'ordre croissant,
- et un entier valeur.
La fonction renvoie -1 si valeur n'est pas élément du tableau et renvoie l'indice d'une occurrence de valeur dans tab si valeur est élément du tableau.
fonction recherche(tab, valeur):
gauche ← 0
droite ← longueur(tab)-1
tant que gauche <= droite:
m ← quotient de (gauche+droite) divisé par 2
Si valeur = tab[m]:
renvoyer m
sinon:
si valeur < tab[m]:
droite ← m-1
sinon:
gauche ← m+1
renvoyer -1
- Est ce que
gaucheest un variant de la boucle? - Est ce que
droiteest un variant de la boucle?
réponse
Non.
Dans le code:
si valeur < tab[m]:
droite ← m-1
sinon:
gauche ← m+1
il est clair que les variables gauche et droite peuvent, lors de certains passages dans
la boucle, n'être pas modifiées. Elles ne peuvent donc pas garantir la terminaison de la boucle
(on pourrait imaginer une situation où l'une des variables prend une inifinité de fois la même valeur:
même si cette variable ne prend qu'un nombre fini de valeurs distinctes, elle ne peut plus garantir la terminaison).
- Démontrer que v = droite - gauche est un variant de la boucle tant que.
- En déduire que l'algorithme termine nécessairement.
réponse
- gauche et droite sont des entiers donc v= droite - gauche est un entier.
- A chaque passage dans la boucle, on a droite - gauche ≥ 0 (puisque c'est la condition pour entrer dans la boucle).
- A chaque passage dans la boucle:
- soit on sort de la boucle (par l'instruction return)
- soit droite est décrémentée d'une unité et donc v est décrémentée d'une unité.
- soit gauche est augmentée d'une unité et donc v est décrémentée d'une unité.
Chaque passage dans la boucle qui ne fait pas sortir de la boucle voit donc v diminuer strictement.
v prend donc des valeurs entières positives strictement décroissantes: v est un variant de boucle.
Conclusion: la boucle termine.