Le nombre exact de comparaisons

Notons $C(n)$ le nombre maximal d'appels à la comparaison sur un tableau de $n$ cases. Un appel élimine la case médiane, et laisse au plus $\lfloor n/2\rfloor$ cases : $C(0)=0$ et $C(n)=1+C(\lfloor n/2\rfloor )$. D'où

$$C(n)=\lfloor {\log }_{2}n\rfloor +1(n\ge 1).$$

Vérification en instrumentant la recherche et en la lançant sur toutes les valeurs possibles, présentes et absentes :

Les valeurs du cours sont donc exactes : $\lfloor {\log }_{2}10^6\rfloor +1=20$ et $\lfloor {\log }_{2}10^9\rfloor +1=30$.

Le détail qui compte. $C(1000)=10$ mais $C(1024)=11$ : la formule saute d'une unité aux puissances de deux, pas ailleurs. Multiplier $n$ par $1000$ ajoute presque exactement $10$ ; multiplier par $2$ ajoute $1$. C'est la définition du logarithme, et c'est ce qui rend la dichotomie insensible à la taille des données.

Une conséquence pratique. Un tableau de $10^9$ entiers occupe $8$ gigaoctets et se cherche en $30$ comparaisons ; le simple fait de lire ce tableau une fois en coûterait $10^9$. La dichotomie est plus rapide qu'un parcours de ce qu'elle cherche — c'est le seul algorithme de ce livre dont on puisse le dire.