Combien de comparaisons, au mieux ?

Un algorithme de recherche doit pouvoir distinguer $n+1$ issues possibles (les $n$ indices du tableau, ou le cas "absent"). Chaque comparaison binaire apporte 1 bit d'information (soit 2 issues possibles, vrai ou faux). Après $k$ comparaisons, l'arbre de décision possède au plus $2^k$ feuilles. Pour pouvoir distinguer les $n+1$ résultats possibles, le nombre de comparaisons $k$ doit vérifier : $$2^k\ge n+1⟹k\ge {\log }_2(n+1)$$ La recherche dichotomique réalise au plus $\lfloor {\log }_{2}n\rfloor +1\approx {\log }_2(n+1)$ comparaisons. Elle est donc optimale à une comparaison près.