Terminaison

En utilisant le principe des variants, montrer que l'algorithme de dichotomie (rappelé ci-dessous) termine toujours.

programme dichotomie

def milieu(i, j):
    """
    i -- entier
    j -- entier

    renvoie le milieu entier de [i,j]
    """
    return (i+j)//2


def dichotomie(valeur, tab):
    """
    tab -- liste d'entiers, triée en ordre croissant
    valeur -- entier

    renvoie True si valeur est dans tab, False sinon.
    La recherche est faite suivant le principe de dichotomie.
    """
    gauche, droite = 0, len(tab)-1
    centre = milieu(gauche, droite)

    while gauche <= droite:
        if tab[centre] == valeur: return True
        if tab[centre] < valeur:
            gauche, droite = centre+1, droite
        else:
            gauche, droite = gauche, centre-1
        centre = milieu(gauche, droite)
    return False

Aide

Montrer que la quantité droite - gauche est un variant de la boucle.

Preuve de terminaison

• droite - gauche est entier.
• droite - gauche $\geqslant 0$ tant qu'on est dans la boucle.
• A chaque étape:
  • Si la valeur cherchée est tab[milieu], on stoppe la boucle.
  • Sinon
    centre = milieu(gauche, droite) donc gauche $\leqslant$ centre $\leqslant$ droite.
    • soit gauche = centre+1 (et droite est inchangé): gauche augmente strictement donc droite-gauche diminue strictement.
    • soit droite = centre-1 (et gauche est inchangé): droite diminue strictement donc droite-gauche diminue strictement.

Donc, si on ne sort pas de la boucle par return True, l'entier positif droite-gauche décroît strictement lors de chaque passage dans la boucle: c'est un variant de boucle. La boucle termine donc nécessairement.