Le module bisect fournit la dichotomie de la bibliothèque standard

import bisect

t = [1, 3, 5, 7, 9]
assert bisect.bisect_left(t, 5) == 2      # AVANT l'occurrence existante
assert bisect.bisect_right(t, 5) == 3     # APRES
assert bisect.bisect_left(t, 4) == 2      # identiques si la valeur est absente

for _ in range(2000):
    t = sorted(random.randint(0, 20) for _ in range(random.randint(0, 10)))
    v = random.randint(-1, 21)
    assert bisect.bisect_left(t, v) == rang_insertion(t, v)

liste = []
for v in [5, 1, 9, 3]:
    bisect.insort(liste, v)
assert liste == [1, 3, 5, 9]

**Notre rang_insertion est bisect_left** : deux mille tirages le confirment, doublons compris. Les deux variantes de la bibliothèque correspondent exactement aux deux décisions possibles sur les égalités — celles qu'un exercice de TD a obligé à trancher.

Un piège de insort. La recherche du point d'insertion est logarithmique, mais l'insertion elle-même décale tous les éléments suivants : elle est linéaire. Maintenir une liste triée par mille insertions ne coûte donc pas mille fois $\log$, mais bien davantage. C'est l'objet de l'exercice suivant.