/*Le but de cet exercice est de faire une recherche dichotomique dans un tableau trie pour trouver la place d'une cle. La fonctionnalite precise de la fonction recherche est indiquee plus bas a l'endroit du corps de cette fonction.
Le principe d'une recherche dichotomique dans un tableau trie tab est le suivant :
- on compare la cle a la donnee que est au milieu du tableau
- si la cle est egale a la donnee mediane, on a trouve sa place
- si la cle est plus petite que la donnee mediane, on recommence avec le tableau de gauche et sinon on recommence avec le tableau de droite.
On n'utilisera pas ici de recursivite*/

#include <stdio.h>

enum {MAXDONNEES=20};

int tab[MAXDONNEES];

int lire(void);
void trier(int);
void afficher(int);
void rechercher(int,int);

void main()
{
  int NbrDonnees,cle;

  NbrDonnees=lire();
  if (NbrDonnees>0)
    {
      trier(NbrDonnees);
      afficher( NbrDonnees);
      printf("\nIndiquez la donnee que vous voulez "
	     "rechercher dans le tableau trie : ");
      scanf("%d",&cle);
      while (cle!=-1)
	{
	  rechercher(NbrDonnees,cle);
	  printf("\nIndiquez la cle que vous voulez "
		 "rechercher dans le tableau trié\n"
		 "(taper -1 si vous n'avez plus de cle à rechercher) : ");
	  scanf("%d",&cle);
	}
    } 
}

int lire()
{
  int donnee,nbr=0;
  char ecrit=0; /*Sert à ecrire une seule fois le message de depassement,
		  les entiers surnumeraires etant néanmoins lus pour etre purges*/
		    
		    printf("\nEntrez les donnees entieres positives, sur une ligne, "
			   "separees par des blancs.\nTerminer la saisie en tapant -1.\n"
			   "Vous avez droit à au plus %d valeurs\n",MAXDONNEES);
  scanf("%d",&donnee);
  while(donnee!=-1)
    {
      if((nbr==MAXDONNEES)&&(!ecrit))
	{
	  printf("\nvous avez donné plus de %d entiers, seuls les %d "
		 "premiers seront pris en compte\n",MAXDONNEES,MAXDONNEES);
	  ecrit=1;
	}
      else  if(nbr<MAXDONNEES)
	{
	  tab[nbr]=donnee;
	  nbr++;
	} 
      scanf("%d",&donnee);
    }
  return nbr;
}

void trier(int nombre)
{
  int i,j,cle;
  
  
  for (i=1;i<nombre;i++)
    {
      cle = tab[i];
      for (j=i-1;(j>=0)&&cle<tab[j];j--) tab[j+1]=tab[j];
      tab[j+1]=cle;
    }
}
/*Cette fonction effectue la tache suivante  :
- si la cle ne figure pas, elle indique par un affichage,
       soit que la cle est plus petite que la plus petite donnee
       soit que la cle est plus grande que la plus grande donnee
       soit que la cle se situe entre deux places precisees du tableau
- si la cle figure, elle indique sa place (qui est comprise entre 1 et nombre)*/

void rechercher(int nombre,int cle)
{
  
/*A COMPLETER en utilisant une recherche dichotomique*/
}

void afficher(int nombre)
{
  int i;
  
  printf("\nvoici le tableau trie\n");
  for(i=0;i<nombre;i++) printf("%5d",tab[i]);
  printf("\n");
}