Correction

On prouve la correction de l'algorithme de dichotomie en explicitant un invariant de boucle.

Note

La notion d'invariant de boucle est travaillée plus systématiquement dans un autre cours.

programme dichotomie

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

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


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

    renvoie True si valeurCherchee 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] == valeurCherchee: return True
        if tab[centre] < valeurCherchee:
            gauche, droite = centre+1, droite
        else:
            gauche, droite = gauche, centre-1
        centre = milieu(gauche, droite)

    return False

Question 1

On se place d'abord dans le cas où la liste donnée en entrée contient la valeurCherchee donnée en paramètre.

L'invariant que l'on va chercher à prouver:

«Tout indice tel que tab[indice] == valeurCherchee vérifie gauche ≤ indice ≤ droite.»

Vérifier que cette propriété est satisfaite avant la boucle.

Justification

Avant d'entrer dans la boucle (ligne marquée #), on a gauche = 0 et droite = len(tab)-1. Comme on est dans le cas où valeurCherchee est présent et que tout indice vérifie 0 ≤ indice ≤ len(tab)-1, la propriété est satisfaite.

Question 2

On se place toujours dans le cas où la liste donnée en entrée contient la valeurCherchee donnée en paramètre.

On suppose être arrivé à une étape pour laquelle on a en début de boucle (ligne 23):

«Tout indice tel que tab[indice] == valeurCherchee vérifie gauche ≤ indice ≤ droite.»

programme dichotomie

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

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


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

    renvoie True si valeurCherchee 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] == valeurCherchee: return True
        if tab[centre] < valeurCherchee:
            gauche, droite = centre+1, droite
        else:
            gauche, droite = gauche, centre-1
        centre = milieu(gauche, droite)

    return False

On note gauche_e, droite_e, centre_e les valeurs des variables gauche, droite, centre en début de passage (ligne 23) (On a bien sûr centre_e = (gauche_e + droite_e)//2).

On notera gauche_f, droite_f, centre_f les valeurs des variables gauche, droite, centre en fin de passage (ligne 30).

Justifier que la propriété
«Tout indice tel que tab[indice] == valeurCherchee vérifie gauche ≤ indice ≤ droite.»
est encore vérifiée en fin de passage dans la boucle

Argumentation

Le corps de boucle est

 while gauche <= droite:

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

• Si tab[centre] == valeurCherchee, on sort de la boucle et de la fonction (en renvoyant l'indice centre). Dans ce cas, gauche, droite, centre n'ont pas changé de valeur: la propriété est encore vérifiée.

• Sinon.

  • Soit tab[centre] < valeurCherchee: dans ce cas, la liste étant ordonnée croissante, valeurCherchee se trouve strictement à droite de centre. Donc en posant gauche_f = centre_e+1 et droite_f = droite_e, la propriété est encore vraie en fin de passage dans la boucle.
  • Soit tab[centre] > valeurCherchee: dans ce cas, la liste étant ordonnée croissante, valeurCherchee se trouve strictement à gauche de centre. Donc en posant gauche_f = gauche_e et droite_f = centre_e-1, la propriété est encore vraie en fin de passage dans la boucle.

Dans tous les cas, en fin de passage dans la boucle, la propriété est encore vraie.

Question 3

En déduire que soit valeurCherchee est présente dans tab et la fonction renvoie True,
soit valeurCherchee n'est pas élément de tab et la fonction renvoie False.

Argumentation

• Si valeurCherchee est élément de tab, on ne sortira pas de la boucle par gauche > droite. En effet, nous avons établi que lorsque valeurCherchee est présente dans tab, on a à chaque fin de passage dans la boucle l'indice de valeurCherchee tel que gauche ≤ indice ≤ droite. Si on sort par gauche > droite, la propriété ne peut être satisfaite: contradiction. Si valeurCherchee est présente, on sort donc nécessairement de la boucle par la ligne ̀if tab[centre] == valeurCherchee: return True et la fonction renvoie bien True.
• Si valeurCherchee n'est pas élément de tab. Alors la condition tab[centre] == valeurCherchee n'est jamais satisfaite, donc on sort de la boucle par gauche > droite et la fonction renvoie False.