Le tableau est noté T, il a N éléments, la valeur cherchée est notée X. Nous voulons un indice r vérifiant

• si X est dans T, alors X = T[r],
• sinon, r est l’indice de la case du tableau dans laquelle il faut placer X si on veut l’ajouter à T en maintenant ce dernier trié.

La recherche dichotomique est un algorithme puissant mais subtil, il est facile d’en écrire des versions qui négligent des cas particuliers. Pour nous assurer que nous avons une version juste, nous allons préciser soigneusement une propriété préservée par notre algorithme, dont on pourra déduire la correction du programme. On travaillera avec deux indices g et d vérifiant :

0 <= g <= d <= N-1 , 0 <= i T[i] < X et d = X (1)

       0               g           m           d              N-1
      +---------------+-----------+-+-----------+---------------+
    T |   T[i] = X   |
      +---------------+-----------+-+-----------+---------------+

Ainsi, si X appartient au tableau son indice est nécessairement compris entre g et d+1. S’il n’y est pas, l’indice de la case où il faudrait le placer est compris également entre g et d+1.

Initialement on pose g = 0 et d = N-1 ; la propriété (1) est vraie. Une itération de l’algorithme consiste à modifier g et d de sorte que l’intervalle [g, d] soit remplacé par un intervalle moitié moins long (à 1/2 près) et que la propriété soit maintenue.

On effectue des itérations tant que g <= d (c.-à-d. tant que l’intervalle [g,d] n’est pas vide). Lorsque la boucle s’arrête, on a d = g-1

       0                     d g                              N-1
      +-----------------------+---------------------------------+
    T |       T[i] = X            |
      +-----------------------+---------------------------------+

et, puisque la propriété est toujours vraie (voir figure) on en déduit que r = g. Si g < N, la comparaison de T[g] et X permet de conclure à propos de la présence ou l’absence de X dans T.

Voici la programmation de la recherche dichotomique. Pour la tester, nous l’avons associée à l’ajout de X lorsque celui-ci n’est pas présent dans T, le tout répété, à partir d’un tableau vide, jusqu’à la frappe d’un nombre négatif :

#include 

#define MAXT 100

int T[MAXT], N, X, g, d, m, i;

int main(void) {
    N = 0;

    printf("? ");
    scanf("%d", &X);
    while (X >= 0) {

/*** la recherche dichotomique est ceci ************/

        g = 0;
        d = N - 1;
        while (g <= d) {
            m = (g + d) / 2;
            if (T[m] < X)
                g = m + 1;
            else
                d = m - 1;
        }

/***************************************************/

        if (g < N && T[g] == X)
            printf("present, i = %d\n", g);
        else {
            printf("absent,  i = %d\n", g);

                                     /* insertion */
            if (N = g; i--)
                    T[i + 1] = T[i];
                T[g] = X;
                N++;
            }
            else
                printf("le tableau est plein\n");
        }

                         /* affichage de controle */
        for (i = 0; i < N; i++)
            printf("%d ", T[i]);
        printf("\n");

        printf("? ");
        scanf("%d", &X);
    }
}

L’importance de la recherche dichotomique réside dans son efficacité. La longueur de l’intervalle [g,d], qui au départ est [0, N-1], est divisée par deux à chaque itération : elle vaut N, puis N/2, N/4, et, au bout de kitérations, N/2^k. Pour avoir N/2^k = 1 il faut k = log₂ N ; par conséquent, le nombre d’opérations de la recherche dichotomique est de l’ordre de  log₂ N.

Cette complexité est à comparer avec celle de la recherche séquentielle (exercice 3), dont nous avons vu qu’elle était de N / 2 en moyenne. Pour fixer les idées, si N = 1.000.000, alors N / 2 = 500.000 et  log₂ N = 20 environ. C’est payant !

Il faut cependant modérer son enthousiasme, car la recherche dichotomique requiert un tableau trié, ce qui rend les insertions très onéreuses. Regardez le programme précédent : l’insertion d’un élément à la place requise par l’ordre nécessite l déplacement d’un cran de N / 2 éléments en moyenne : insérer dans un tableau trié est aussi coûteux que faire une recherche séquentielle..

Si un programme fait surtout des recherches, ce qui vient d’être dit est tout à fait valable. S’il y a beaucoup d’insertions il faudra utiliser une méthode où les recherches et les insertions seront optimisées (par exemple un arbre binaire ou une table de hash-code).