Où insérer dans une liste triée

Le code.

def position(L, x):
    # L est TRIEE ; renvoie l'indice d'insertion de x
    a, b = 0, len(L)          # b vaut len(L), pas len(L) - 1
    while a < b:
        m = (a + b) // 2
        if L[m] < x:
            a = m + 1         # x va strictement a droite de m
        else:
            b = m             # x peut aller en m, ou avant
    return a

L = [2, 5, 5, 8, 13]
print(position(L, 6))     # 3
print(position(L, 0))     # 0   plus petit que tous
print(position(L, 20))    # 5   plus grand que tous
print(position(L, 5))     # 1   devant les 5 deja presents

Ce que l'invariant garantit. À chaque tour, l'indice cherché est dans $[[a,b]]$ : tout élément d'indice $<a$ est strictement inférieur à x, et tout élément d'indice $\ge b$ est supérieur ou égal à x. Les deux affectations préservent cette propriété — c'est pourquoi b = m et non b = m - 1 : l'indice m reste candidat quand L[m] >= x.

Terminaison. À chaque tour, $b-a$ diminue strictement. En effet $a\le m<b$, donc l'affectation a = m + 1 fait croître $a$, et b = m fait décroître $b$. La boucle s'arrête donc, après environ ${\log }_{2}n$ tours.

Les cas extrêmes, à tester systématiquement. Pour x = 0, la condition L[m] < x n'est jamais vraie, b descend jusqu'à $0$ et la fonction rend $0$ — insertion en tête. Pour x = 20, la condition est toujours vraie, a monte jusqu'à $5=$ len(L) — insertion en queue. C'est parce que b est initialisé à len(L) et non à len(L) - 1 que ce second cas fonctionne : sinon l'indice $5$ serait inatteignable, et l'insertion en queue impossible.

Les doublons. Avec L[m] < x (inégalité stricte), l'indice rendu est celui de la première occurrence de x s'il y en a. Avec L[m] <= x on obtiendrait la position après la dernière. Les deux conventions sont défendables, mais il faut savoir laquelle on programme.