Sur un tableau contenant plusieurs fois la même valeur, quelle…

La mesure d'abord.

assert dichotomie([2, 2, 2, 2, 2], 2) == 2      # celle du MILIEU
assert dichotomie([1, 2, 2, 3], 2) == 1
assert dichotomie([1, 2, 2, 2], 2) == 1

Elle renvoie une occurrence, celle sur laquelle la coupe tombe — pas la première, pas la dernière. Sur cinq $2$ identiques, c'est celle d'indice $2$.

La docstring du cours ne promet rien de plus, et c'est ce qui la rend correcte : elle dit « l'indice d'une occurrence de $v$ », et la postcondition s'écrit t[r] == v. Une docstring qui aurait annoncé « la première occurrence » serait fausse — et fausse d'une manière que les tests sur des tableaux sans doublon ne révèleraient jamais.

Si l'on veut vraiment la première, l'exercice précédent l'a déjà écrite :

def premiere_occurrence(t, v):
    """Indice de la PREMIERE occurrence de v dans t trie, ou -1.

    Postcondition : si r != -1 alors t[r] == v et (r == 0 ou t[r-1] < v).
    """
    r = rang_insertion(t, v)
    if r < len(t) and t[r] == v:
        assert r == 0 or t[r - 1] < v
        return r
    return -1

assert premiere_occurrence([2, 2, 2, 2, 2], 2) == 0
assert premiere_occurrence([1, 2, 2, 3], 2) == 1
assert premiere_occurrence([1, 3], 2) == -1
assert premiere_occurrence([], 2) == -1

for _ in range(3000):
    t = sorted(random.randint(0, 8) for _ in range(random.randint(0, 12)))
    v = random.randint(0, 8)
    r = premiere_occurrence(t, v)
    assert r == (t.index(v) if v in t else -1)

La postcondition « $r=0$ ou $t[r-1]<v$ » dit exactement « rien avant $r$ ne vaut $v$ », et c'est elle qu'on ne pouvait pas écrire pour la version du cours. Le test aléatoire se compare à t.index, la fonction de la bibliothèque qui, elle, promet la première occurrence — et qui parcourt le tableau, là où la nôtre reste logarithmique.

Des deux corrections possibles, la bonne est presque toujours la docstring : c'est elle qui mentait. On n'écrit un algorithme plus contraignant que si le programme a besoin de cette garantie.