Exercice langage C : Recherche Dichotomique

Travail à Faire :

RECHERCHE DICHOTOMIQUE DANS UN TABLEAU ORDONNE. On considère un tableau U de I nombres entiers deux à deux distincts, rangés par ordre croissant, et un nombre Y. Ecrivez un programme qui détermine l’indice exprimant soit le rang de Y dans U soit, si Y ne figure pas dans U, le rang de l’emplacement dans lequel il faudrait ranger Y pour l’insérer dans le tableau, en conservant trié ce dernier.

Principe : considérer deux indices v et w tels que le sous-tableau [ ? … ? ] soit seul susceptible de contenir Y (initialement, v = 0 et w = I-1). En comparant Y et l’élément du milieu, déterminer celle des deux moitiés du sous-tableau qui est susceptible de contenir Y. Recommencer cette opération jusqu’à déterminer une unique position du tableau.

Estimez le nombre moyen d’opérations faites par ce programme et par celui du n° 4. Estimez le nombre moyen d’opérations faites par l’une et l’autre méthode, lorsque la recherche d’un élément qui ne figure pas dans le tableau doit être suivie de son insertion.

[1] 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 , 0 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 (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 , 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 m = (g + d) / 2;
if (T[m] g = m + 1;
else
d = m - 1;
}
/***************************************************/
if (g 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 printf("%d ", T[i]);
printf("\n");
printf("? ");
scanf("%d", &X);
}
}

[2] 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).