Écrire est trie(t) et l'utiliser comme précondition explicite

Le mensonge, en deux cases.

assert dichotomie([2, 1], 1) == -1      # 1 EST dans le tableau

C'est le plus petit contre-exemple qui existe : milieu = 0, t[0] = 2 > 1, donc la fonction cherche à gauche… et il n'y a rien à gauche. Elle répond « absente » pour une valeur présente. Sur un tableau plus grand, le défaut est encore plus perfide :

mauvais = [5, 1, 9, 3, 7]
assert dichotomie(mauvais, 3) == -1     # ABSENT, alors que 3 y est
assert dichotomie(mauvais, 9) == 2      # ... et JUSTE sur la voisine

La même fonction, sur le même tableau, est tantôt juste tantôt fausse : rien dans son comportement ne prévient. Mesuré sur $2000$ tableaux non triés de huit éléments, elle déclare absente une valeur présente environ une fois sur deux.

def est_trie(t):
    """True si t est croissant au sens large. Cout : n-1 comparaisons."""
    for i in range(len(t) - 1):
        if t[i] > t[i + 1]:
            return False
    return True


def dichotomie_verifiee(t, v):
    assert est_trie(t), "tableau non trie"
    return dichotomie(t, v)

Le coût, mesuré. Sur un tableau de $200000$ éléments, $200$ recherches :

Un facteur cinq mille. La raison est structurelle et non anecdotique : est_trie est linéaire quand la dichotomie est logarithmique. Vérifier la précondition à chaque appel coûte donc infiniment plus cher que la recherche elle-même — et revient à parcourir tout le tableau, c'est-à-dire à faire exactement ce que la dichotomie voulait éviter.

La conclusion, qui est la vraie leçon de l'exercice. Une précondition n'est pas toujours à vérifier par la fonction : ici, c'est à l'appelant de garantir que son tableau est trié, et la docstring est le contrat qui le lui dit. On vérifie une fois, au moment où l'on trie ; pas à chaque interrogation. En développement, on peut activer les assert et les désactiver ensuite — c'est même l'une des raisons d'être du mot-clé.