#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 donnée que vous voulez "
	     "rechercher dans le tableau trie : ");
      scanf("%d",&cle);
      while (cle!=-1)
	{
	  rechercher(NbrDonnees,cle);
	  printf("\nIndiquez la donnee que vous voulez "
		 "rechercher dans le tableau trié\n"
		 "(taper -1 si vous n'avez plus de donnee à 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;
    }
}

void rechercher(int nombre,int cle)
{
  int gauche, droite, milieu;
  
  if (cle<tab[0])
    {
      printf("votre donnée est inférieure à la plus petite donnée du tableau\n");
      return;
    }
  if (cle>tab[nombre-1])
    {
      printf("votre donnée est supérieure à la plus grande donnée du tableau\n");
      return;
    }
  if (cle==tab[nombre-1])
    {
      printf("votre donnée est dans le tableau à la place %d\n",nombre);
      return;
    }
  gauche=0;
  droite=nombre-1;
  /*Les indices gauche et droite seront gérés de telle sorte que
    l'on ait toujours : tab[gauche]<=cle<tab[droite]*/
  while (gauche+1<droite)
    {
      milieu=(gauche+droite)/2;
      if (cle<tab[milieu]) droite=milieu;
      else gauche=milieu;
    }
  /*on a nécessairement droite=gauche+1*/
  if (cle==tab[gauche])
    printf("votre donnée est dans le tableau à la place %d\n",gauche+1);
  else 
    printf("votre donnée n'est pas dans le tableau ; "
	   "sa place est entre les places %d et %d\n",gauche+1,gauche+2);
}

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