La complexité logarithmique

La recherche dichotomique est en O(log n), où n est le nombre d'éléments du tableau. Ce logarithme (en base 2) répond à une question simple : combien de fois peut-on diviser n par 2 avant d'obtenir 1 ? C'est exactement le nombre d'étapes nécessaires dans le pire des cas.

Regarde comment le nombre d'étapes croît très lentement par rapport à la taille du tableau :

n (taille)        etapes maximum (log2(n) arrondi au superieur)
8                 3    (8 -> 4 -> 2 -> 1)
16                4    (16 -> 8 -> 4 -> 2 -> 1)
1 000             10
1 000 000         20
1 000 000 000     30

Multiplier la taille du tableau par 1000 (de 1 000 à 1 000 000) n'ajoute que 10 étapes environ, alors qu'une recherche linéaire (élément par élément) verrait son nombre de comparaisons multiplié par 1000 dans le pire cas. C'est pourquoi la dichotomie est si précieuse sur de grandes quantités de données : chercher dans un milliard d'éléments ne prend qu'une trentaine de comparaisons.

On peut visualiser la réduction de l'intervalle comme un arbre : chaque étape divise la taille de la zone restante par deux, jusqu'à atteindre une zone d'un seul élément.

taille 16
   |
   v (divise par 2)
taille 8
   |
   v
taille 4
   |
   v
taille 2
   |
   v
taille 1   (fin : on a trouve ou la cible est absente)

À retenir : cette complexité logarithmique suppose que le tableau soit déjà trié. Si le tableau n'est pas trié, il faut d'abord le trier (coût O(n log n) avec un bon tri), sauf si on ne fait qu'une seule recherche, où une recherche linéaire directe en O(n) reste parfois plus simple et plus rapide au total.