Trier une chaîne ne rend pas la recherche logarithmique

Mesuré, en comptant les maillons ou cases visités pour $2n$ recherches (la moitié réussies, la moitié infructueuses) dans une structure de $n$ éléments :

n = 1000  liste NON triee            1 500 500 visites
          liste TRIEE                1 001 999 visites
          tableau trie (dichotomie)     18 964 visites
n = 4000  liste NON triee           24 002 000 visites
          liste TRIEE               16 007 999 visites
          tableau trie (dichotomie)     91 822 visites

Trier la chaîne apporte un facteur $1,5$, et rien de plus. Le gain est réel — sur une recherche infructueuse, on s'arrête dès qu'on dépasse la valeur cherchée, soit en moyenne à la moitié — mais le coût reste $\Theta (n)$ par recherche. Le passage de $24$ millions à $16$ millions de visites est un facteur constant ; le passage à $91822$ est un changement d'ordre.

La raison, et c'est le point du chapitre. La dichotomie a besoin d'atteindre la case du milieu en $O(1)$. C'est l'accès par indice qui la rend possible, pas le tri. Une chaîne n'a pas d'indice : pour atteindre son milieu, il faut la parcourir jusque-là, et l'on a déjà payé le prix qu'on voulait éviter.

Autrement dit, la ligne « tableau trié : $O(\log n)$ » du récapitulatif repose sur deux propriétés, et non une : l'ordre et l'accès direct. Enlever l'une des deux fait tomber la complexité.

La conclusion à en tirer pour la suite du livre. Si l'on veut à la fois des insertions bon marché et une recherche logarithmique, il faut une structure qui donne un « milieu » sans indice : c'est exactement ce que fournit l'arbre binaire de recherche du chapitre chap:tas, où le nœud racine joue le rôle du milieu.