#include<stdio.h>

enum { MAX = 10};

int saisit(int *);
void affiche (int *, int);
int chercheIndice(int *, int, int);
void insere(int *, int, int, int);

int main(void)
{
  int table[MAX];  /* pour ranger les entiers saisis */
  int nbEntiers;  /* nombre d'entiers saisis */
  
  printf("Programme d'insertion dichotomique \n\n");
  nbEntiers = saisit(table);
  printf("Contenu du tableau\n");
  affiche(table, nbEntiers);
  return 0;
}

int saisit(int * tableau)
{
  int nbASaisir; /* nombre d'entiers que l'utilisateur va indiquer */
  int nbEntiers = 0; /* nombre d'entiers distincts deja saisis */
  int i, cle, indice;

  do
    {
      printf("entrez le nombre d'entiers que vous voulez saisir,"
	     " sans dépasser %d\n",MAX);
      scanf("%d", &nbASaisir);
    } while (nbEntiers > MAX);
  printf("Indiquez les %d entiers\n", nbASaisir);
  for(i = 0; i < nbASaisir; i++) 
    {
      scanf("%d", &cle);
      indice =  chercheIndice(tableau, nbEntiers, cle);
      if (indice == -1) printf("%d figure deja\n", cle);
      else 
	{
	  insere(tableau, nbEntiers, cle, indice);
	  nbEntiers++;
	}
    }
  return nbEntiers;
}

int chercheIndice(int * tableau, int nbEntiers, int cle)
{
  int gauche = 0, droite = nbEntiers - 1;
  int milieu;
  
  while (gauche <= droite)
    {
      milieu = (gauche + droite) / 2;
      if (cle < tableau[milieu]) droite = milieu - 1;
      else if (cle > tableau[milieu]) gauche = milieu + 1;
      else  return -1;
    }
  return gauche;
}

void insere(int * tableau, int nbEntiers, int cle, int place)
{
  int i;

  for(i = nbEntiers; i > place; i--) tableau[i] = tableau[i - 1];
  tableau[place] = cle;
}


void affiche (int * tableau, int nbEntiers)
{
  int i;
  
  for(i = 0; i < nbEntiers; i++) printf("%4d",tableau[i]);
  printf("\n");
}