Exercice langage C recherche d’une valeur dans un tableau

a) La recherche séquentielle

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

#include <stdio.h>
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<N; 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; I<N; I++)
     printf("%d ", A[I]);
 printf("\n");
 /* Recherche de la position de la valeur */
 POS = -1;
 for (I=0 ; (I<N)&&(POS==-1) ; I++)
       if (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;
}

b) La recherche dichotomique (‘recherche binaire’, ‘binary search’)

#include <stdio.h>
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<N; 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; I<N; I++)
    printf("%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<=SUP) && (POS==-1))
        {
         MIL=(SUP+INF)/2;
         if (VAL < A[MIL])
               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.