Exercice langage C recherche d'une valeur dans un tableau

Problème: Rechercher dans un tableau d'entiers A une valeur VAL entrée au clavier. Afficher la position de VAL si elle se trouve dans le tableau, sinon afficher un message correspondant. La valeur POS qui est utilisée pour mémoriser la position de la valeur dans le tableau, aura la valeur -1 aussi longtemps que VAL n'a pas été trouvée.

Implémenter deux versions:

a) La recherche séquentielle

Comparer successivement les valeurs du tableau avec la valeur donnée.

b) La recherche dichotomique ('recherche binaire', 'binary search')

Condition: Le tableau A doit être trié

Comparer le nombre recherché à la valeur au milieu du tableau,

• s'il y a égalité ou si le tableau est épuisé, arrêter le traitement avec un message correspondant.
• si la valeur recherchée précède la valeur actuelle du tableau, continuer la recherche dans le demi-tableau à gauche de la position actuelle.
• si la valeur recherchée suit la valeur actuelle du tableau, continuer la recherche dans le demi-tableau à droite de la position actuelle.

Ecrire le programme pour le cas où le tableau A est trié par ordre croissant.

Question: Quel est l'avantage de la recherche dichotomique? Expliquer brièvement.

#include
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int VAL; /* valeur à rechercher */
int POS; /* position de la valeur */
int N; /* dimension */
int I; /* indice courant */

/* Saisie des données */
printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );
for (I=0; I{
printf("Elément %d : ", I);
scanf("%d", &A[I]);
}
printf("Elément à rechercher : ");
scanf("%d", &VAL );
/* Affichage du tableau */
printf("Tableau donné : \n");
for (I=0; Iprintf("%d ", A[I]);
printf("\n");
/* Recherche de la position de la valeur */
POS = -1;
for (I=0 ; (Iif (A[I]==VAL)
POS=I;
/* Edition du résultat */
if (POS==-1)
printf("La valeur recherchée ne se trouve pas "
"dans le tableau.\n");
else
printf("La valeur %d se trouve à la position %d. \n",
VAL, POS);
return 0;
}

a) La recherche séquentielle

Comparer successivement les valeurs du tableau avec la valeur donnée.

b) La recherche dichotomique ('recherche binaire', 'binary search')

#include
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int VAL; /* valeur à rechercher */
int POS; /* position de la valeur */
int N; /* dimension */
int I; /* indice courant */
int INF, MIL, SUP; /* limites du champ de recherche */
/* Saisie des données */
printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );
for (I=0; I{
printf("Elément %d : ", I);
scanf("%d", &A[I]);
}
printf("Elément à rechercher : ");
scanf("%d", &VAL );
/* Affichage du tableau */
printf("Tableau donné : \n");
for (I=0; Iprintf("%d ", A[I]);
printf("\n");
/* Initialisation des limites du domaine de recherche */
INF=0;
SUP=N-1;
/* Recherche de la position de la valeur */
POS=-1;
while ((INF{
MIL=(SUP+INF)/2;
if (VAL SUP=MIL-1;
else if (VAL > A[MIL])
INF=MIL+1;
else
POS=MIL;
}

/* Edition du résultat */
if (POS==-1)
printf("La valeur recherchée ne se trouve pas "
"dans le tableau.\n");
else
printf("La valeur %d se trouve à la position %d. \n",
VAL, POS);
return 0;
}

Question: Quel est l'avantage de la recherche dichotomique?

Dans le pire des cas d'une recherche séquentielle, il faut traverser tout le tableau avant de trouver la valeur ou avant d'être sûr qu'une valeur ne se trouve pas dans le tableau.

Lors de la recherche dichotomique, on élimine la moitié des éléments du tableau à chaque exécution de la boucle. Ainsi, la recherche se termine beaucoup plus rapidement.

La recherche dichotomique devient extrêmement avantageuse pour la recherche dans de grands tableaux (triés) : L'avantage de la recherche dichotomique par rapport à la recherche séquentielle monte alors exponentiellement avec la grandeur du tableau à trier.

Exemple:

Lors de la recherche dans un tableau de 1024 éléments:

• le pire des cas pour la recherche séquentielle peut entraîner 1024 exécutions de la boucle.
• le pire des cas pour la recherche dichotomique peut entraîner 10 exécutions de la boucle.

Lors de la recherche dans un tableau de 1 048 576 éléments:

• le pire des cas pour la recherche séquentielle peut entraîner 1 048 576 exécutions de la boucle.
• le pire des cas pour la recherche dichotomique peut entraîner 20 exécutions de la boucle.