Que renvoie dichotomie sur un tableau vide

assert dichotomie([], 5) == -1
_, trace = dichotomie_tracee([], 5)
assert trace == []          # la boucle n'est JAMAIS entree

Elle renvoie $-1$, et c'est juste. Sur un tableau vide, gauche = 0 et droite = len(t) - 1 = -1 : la condition gauche <= droite est fausse d'emblée, le corps n'est jamais exécuté, et la fonction tombe directement sur return -1. Aucun accès à t[milieu] n'a lieu — c'est pourquoi rien ne plante.

Ce que cela dit de l'invariant. L'invariant est « si $v$ figure dans $t$, son indice est dans $[\text{gauche},\text{droite}]$ ». Sur un tableau vide, cet intervalle est vide dès le départ, et l'invariant est vrai trivialement — la conclusion « $v$ n'y figure pas » suit immédiatement. Un raisonnement correct sur les cas limites ne demande aucun cas particulier dans le code : c'est le signe qu'il est bien construit.

Et le tableau à un élément.

assert dichotomie([5], 5) == 0
assert dichotomie([5], 3) == -1

Ces deux cas-là sont ceux que, d'après Knuth, les premières versions publiées manquaient.