Écrire une variante qui, lorsque v est absente, renvoie l'indice où il…

def rang_insertion(t, v):
    """Indice ou inserer v dans le tableau trie t pour le garder trie.

    Postcondition : t[:r] + [v] + t[r:] est trie, et r est le PREMIER
                    indice tel que t[r] >= v.
    """
    gauche, droite = 0, len(t)
    while gauche < droite:
        milieu = (gauche + droite) // 2
        if t[milieu] < v:
            gauche = milieu + 1
        else:
            droite = milieu
    return gauche

Trois différences avec la version du cours, et chacune compte. D'abord droite = len(t) et non len(t) - 1 : il faut pouvoir renvoyer l'indice $n$, c'est-à-dire « après le dernier ». Ensuite while gauche < droite et non <= : l'intervalle est maintenant semi-ouvert, et la boucle s'arrête quand il est réduit à un point — qui est la réponse. Enfin droite = milieu et non milieu - 1 : le milieu peut lui-même être la bonne position, on n'a pas le droit de l'écarter.

Le variant reste le même — la largeur $\text{droite}-\text{gauche}$ — et il décroît toujours strictement : si t[milieu] < v, gauche passe au-delà de milieu ; sinon droite descend à milieu, ce qui est bien une diminution stricte puisque $\text{milieu}<\text{droite}$ par construction de la division entière. C'est précisément ce dernier point qui interdit d'écrire gauche = milieu dans l'autre branche : la boucle ne terminerait plus.

Vérification.

t = [1, 3, 5, 7, 9]
assert rang_insertion(t, 4) == 2
assert rang_insertion(t, 0) == 0
assert rang_insertion(t, 10) == 5      # apres le dernier
assert rang_insertion(t, 5) == 2       # AVANT l'occurrence existante
assert rang_insertion([], 1) == 0

for _ in range(3000):
    t = sorted(random.randint(0, 20) for _ in range(random.randint(0, 12)))
    v = random.randint(-2, 22)
    r = rang_insertion(t, v)
    nouveau = t[:r] + [v] + t[r:]
    assert nouveau == sorted(nouveau)
    assert all(x < v for x in t[:r]) and all(x >= v for x in t[r:])

Le test aléatoire vérifie la postcondition telle qu'elle est écrite, en deux morceaux : le tableau reconstruit est trié, et la coupure est bien au premier élément $\ge v$. Les tirages comportent des doublons — c'est voulu, car c'est le cas qui distingue « le premier indice $\ge v$ » de « un indice quelconque ».