Complexité☘

L'efficacité de l'algorithme de recherche dichotomique dans un tableau trié peut être mesurée en comptant le nombre de passages dans la boucle au pire des cas, c'est-à-dire lorsque la valeur recherchée ne se trouve pas dans le tableau.

Remarque

Dans cette page et les suivantes, on utilisera la notation Python $a$ // $b$ pour calculer le quotient de deux entiers $a$ et $b$ .

Un exemple pour commencer

Considérons un tableau trié de 100 éléments mais qui ne contient pas la valeur recherchée.
Combien de tours de boucle faut-il pour indiquer que la valeur recherchée n'est pas dans le tableau ?

Au départ, le tableau contient 100 éléments.
On cherche l'indice du milieu : il partage le tableau en deux sous-tableaux contenant soit 49, soit 50 éléments.
On choisit le cas le moins favorable : le tableau examiné contient 50 éléments.
On cherche l'indice du milieu : il partage le tableau en deux sous-tableaux contenant soit 24, soit 25 éléments.
On choisit le cas le moins favorable : le tableau examiné contient 25 éléments.
On cherche l'indice du milieu : il partage le tableau en deux sous-tableaux contenant 12 éléments chacun.
Le tableau examiné contient 12 éléments.
On cherche l'indice du milieu : il partage le tableau en deux sous-tableaux contenant soit 5, soit 6 éléments.
On choisit le cas le moins favorable : le tableau examiné contient 6 éléments.
On cherche l'indice du milieu : il partage le tableau en deux sous-tableaux contenant soit 2, soit 3 éléments.
On choisit le cas le moins favorable : le tableau examiné contient 3 éléments.
On cherche l'indice du milieu : il partage le tableau en deux sous-tableaux contenant 1 élément chacun.
Le tableau examiné contient 1 élément.
Cet élément est examiné puis les sous-tableaux sont vides : le traitement est terminé.

Avec cet algorithme , il suffit donc de 7 tours de boucles au maximum pour déterminer si un élément est présent ou non dans un tableau trié de 100 éléments. Efficace, non ?

Nombre de chiffres en base 10☘

En base 10, le quotient de la division d'un entier par 10 renvoie son nombre de dizaines, c'est-à-dire décale les chiffres de ce nombre d'une position à droite.

Exemple

On considère le nombre $1852$ .

$1852$ // $10$ = $185$ . Il y a bien un décalage vers la droite (et le chiffre des unités « disparaît »).
Le nombre de chiffres de $1852$ s'obtient en comptant le nombre de divisions successives de $1852$ (puis des quotients obtenus) par $10$ nécessaires pour obtenir un quotient nul.
Ces quotients sont respectivement $185$ , $18$ , $1$ et $0$ .
On en déduit que $1852$ contient 4 chiffres

Nombre de chiffres en base 2☘

Dans n'importe quelle base $b$ , le quotient de la division d'un entier par $b$ décale les chiffres de ce nombre d'une position à droite. C'est aussi vrai pour les nombres binaires.

Exemple

On considère le nombre nombre décimal $170$ dont l'écriture binaire est $(10101010)_2$ .
On effectue ensuite des divisions successives de $170$ (puis des quotients obtenus) par $2$ jusqu'à obtenir un quotient nul, et on traduit les quotients obtenus en binaire :

Tout d'abord, $170$ a pour écriture binaire $(10101010)_2$ .
On divise par $2$ : $170$ // $2$ = $85$ , qui a pour écriture binaire $(1010101)_2$ .
On divise par $2$ : $85$ // $2$ = $42$ (quotient entier), qui a pour écriture binaire $(101010)_2$ .
On divise par $2$ : $42$ // $2$ = $21$ , qui a pour écriture binaire $(10101)_2$ .
On divise par $2$ : $21$ // $2$ = $10$ (quotient entier), qui a pour écriture binaire $(1010)_2$ .
On divise par $2$ : $10$ // $2$ = $5$ , qui a pour écriture binaire $(101)_2$ .
On divise par $2$ : $5$ // $2$ = $2$ (quotient entier), qui a pour écriture binaire $(10)_2$ .
On divise par $2$ : $2$ // $2$ = $1$ , qui a pour écriture binaire $(1)_2$ .
On divise par $2$ : $1$ // $2$ = $0$ (quotient entier), qui a pour écriture binaire $(0)_2$ .

C'est terminé : il a fallu 8 divisions successives de $170$ par $2$ pour obtenir un quotient nul, ce qui correspond au nombre de bits dans l'écriture binaire de l'entier $170$ .

Efficacité☘

On rappelle ci-dessous l'algorithme de recherche d'un valeur par dichotomie dans un tableau tab d'entiers trié par ordre croissant, où val est l'entier recherché :

i_debut ← 0
i_fin ← longueur(tab)-1
i_milieu ← (i_debut + i_fin)//2         # indice de l'élément "central"

Tant que i_debut ≤ i_fin :
    Si tab[i_milieu] = val Alors
        Renvoyer Vrai
    Sinon Si tab[i_milieu] < val Alors
        i_debut ← i_milieu+1
    Sinon 
        i_fin ← i_milieu-1
    i_milieu ← (i_debut + i_fin)//2

Renvoyer Faux

Le nombre d'itérations de la boucle (nombre de tours) correspond exactement au nombre de valeurs prises par la variable i_milieu puisqu'à chaque tour de boucle, i_milieu est remplacé par la valeur (i_debut + i_fin)//2.

Comme nous l'avons vu dans le paragraphe précédent, l'opération (i_debut + i_fin)//2 revient à un décalage d'un bit vers la droite de l'écriture binaire de i_debut + i_fin. Les divisions successives de ces valeurs par $2$ permettent alors d'affirmer qu'il y a autant de passages dans la boucle que de bits dans i_debut + i_fin.

Puisque la valeur initiale de i_debut est 0, et puisque celle de i_fin est longueur(tab)-1, alors la valeur initiale de i_debut + i_fin est longueur(tab)-1.

Conclusion

Soit tab un tableau de n éléments triés par ordre croissant et soit val une valeur de même type que les éléments du tableau tab.
L'algorithme de recherche dichotomique dans un tableau trié est très efficace : le nombre maximum d'opérations nécessaire pour déterminer si val est une valeur de tab est le nombre de bits de l'écriture binaire de n.

Méthode☘

Pour déterminer ce nombre maximum d'opérations, il suffit de chercher la plus petite puissance de 2 qui dépasse la taille du tableau. Par exemple :

$2^6 \leq 100 < 2^7$ donc il faut 7 étapes au maximum pour déterminer si une valeur est présente dans un tableau de taille $100$ .
$2^7 \leq 128 < 2^8$ donc il faut 8 étapes au maximum pour déterminer si une valeur est présente dans un tableau de taille $128$ .
$2^{19} \leq 1 000 000 < 2^{20}$ donc il faut 20 étapes au maximum pour déterminer si une valeur est présente dans un tableau de taille $10^6$ .

Pour aller plus loin☘

Soit $n$ le nombre d'éléments dans le tableau trié.
Il existe une fonction mathématique, appelée logarithme de base 2, qui permet de déterminer le plus petit entier $k$ tel que $2^k \leq n < 2^{k+1}$ .
Cette fonction permet de dire que la complexité de l'algorithme de recherche dichotomique est de complexité logarithmique, en $O(log(n))$ .