/* Programme de recherche dichotomique d'un élément dans une liste d'entiers */
/* Fait par MM le 07/09/2000                                                  */
/* Dernière mise à jour : 07/09/2000                                         */

#include<stdio.h>

int main()
{ 

  /* DECLARATION DES VARIABLES */

  /* Liste TRIEE des Ui */
  int iTableau[]={1,2,3,5,6,8,9};
  /* Elément recherché */
  int iRecherche;
  /* Indice du premier élément du sous-tableau */
  int iPremier;
  /* Indice du dernier élément du sous-tableau */
  int iDernier;
  /* Indice de l'élément du milieu du sous-tableau */
  int iMilieu;
  /* Boolean indiquant si l'élément est trouve */
  int iTrouve;
  /* Indication de fin de saisie (0=fin)*/
  int iFin=1;
 
  /* tant que l'utilisateur souhaite saisir des entiers */
  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 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 saisit pas un nombre, on sort du programme */
      if(!isalpha(iFin)) iFin=0;

      /* reprise d'une recherche */
      iTrouve=0;
    }
}