La dichotomie est logarithmique

def comparer(n, essais=20000):
    t = list(range(n))
    cibles = [random.randrange(n) for _ in range(essais)]

    t0 = time.perf_counter()
    for v in cibles:
        dichotomie(t, v)
    t_dicho = time.perf_counter() - t0

    ens = set(t)
    t0 = time.perf_counter()
    for v in cibles:
        v in ens
    t_ens = time.perf_counter() - t0
    return t_dicho, t_ens

Deux lectures, et elles vont dans des sens opposés. D'un côté, la dichotomie tient remarquablement bien : multiplier la taille par mille ne multiplie son temps que par trois — c'est le logarithme, qui passe de $10$ à $20$ tours, plus le coût des accès en mémoire. De l'autre, elle reste vingt à trente fois plus lente que l'ensemble, à toutes les tailles.

Pourquoi la comparaison n'est pas déloyale mais reste incomplète. L'ensemble ne répond qu'à « est-ce là ? » ; la dichotomie donne la position, permet de chercher le voisin le plus proche, le rang d'insertion, un intervalle de valeurs — toutes choses qu'une table de hachage ne sait pas faire, puisqu'elle a perdu l'ordre. Comparer deux structures sur la seule opération qu'elles ont en commun donne un chiffre exact et une conclusion fausse.

Une précaution de mesure, encore. Le temps de construction de l'ensemble n'est pas compté ici, pas plus que celui du tri qu'exige la dichotomie. Sur une seule recherche, ces coûts d'installation dominent tout le reste — c'est le raisonnement du cours sur « trier d'abord, est-ce rentable ? », et il faut le refaire à chaque fois.