Solution de la recherche dichotomique en C

Résolu/Fermé
ahmedbj Messages postés 146 Date d'inscription dimanche 25 mars 2007 Statut Membre Dernière intervention 8 janvier 2013 - 21 oct. 2007 à 20:34
 FOX - 10 avril 2014 à 03:13
Bonjour,
Est-ce quelqu'un peut m'expliquer comment faire une recherche dichotomique d'une valeur dans un tableau d'entier par récursivité en langage C
merci

9 réponses

Bonjour,
Je suis encore Dr.SoFtNaF, il désormait qu'il y a un problème avec le forum, je peux pas m'identifier, ban volà le code source en C

#include<stdio.h>
/* Programme de recherche dichotomique d'un élément dans une liste d'entiers */
int main(){
/* DECLARATION DES VARIABLES */
int iTableau[]={1,2,3,5,6,8,9}; /* Tableau TRIE d’entiers */
int iRecherche; /* Elément recherché */
int iPremier; /* Indice du premier élément du sous-tableau analysé */
int iDernier; /* Indice du dernier élément du sous-tableau analysé */
int iMilieu; /* Indice de l'élément du milieu du sous-tableau analysé */
int iTrouve; /* Booléen indiquant si l'élément est trouvé */
int iFin=1; /* Indication de fin de saisie (0=fin) */
/* Tant que l'utilisateur souhaite faire des recherches */
while(iFin)
{
   printf("Quel élément recherchez-vous ? ");
   scanf("%d",&iRecherche);
  /* Initialisation des variables*/
   iPremier=0;
   iDernier=6;
   iTrouve=0;
   /* Tant qu'on a pas trouve l'élément recherché ou que le sous-tableau */
   /* contient plus de 1 élément */
   while((iPremier <= iDernier)&&(iTrouve==0))
      {
       /* Calcul de la position de l'élément du milieu */
           iMilieu=(iPremier+iDernier)/2;
      /* Si l'élément du milieu est l'élément recherché */
           if(iTableau[iMilieu]==iRecherche) iTrouve =1;
           else
                 {
                 /* Si la valeur recherchée est plus petite */
                 /* que la valeur du l'élément du milieu */
                 /* Alors on regarde le sous-tableau de gauche */
                 if(iTableau[iMilieu]>iRecherche) iDernier = iMilieu -1;
                   /* sinon on regarde le sous-tableau de droite*/
                 else iPremier = iMilieu +1;
                 }
          }
          if(!iTrouve) printf("Cette valeur n'appartient pas à la liste\n");
           else printf("Cette valeur appartient à la liste\n");
         printf("Voulez-vous continuer ? (Taper 0 pour sortir du programme) : ");
            scanf("%d",&iFin);
        /* Si l'utilisateur ne saisait pas un nombre, on sort du programme */
         if(!isalpha(iFin)) iFin=0;

          /* reprise d'une recherche */
        iTrouve=0;
    } /* Fin du while */
   } /* Fin du main */


Bonne continuation

Dr.SoFtNaF
10
excellent algorithme
0