#include <stdio.h>
#include <stdlib.h>

/* Retourne 1 (vrai) si le tableau est trie       */
/* Retourne 0 (faux) si le tableau n'est pas trie */
int estTrie(int tab[], int n)          /* n : la taille du tableau tab */
{
 int trie = 1; /* vrai par defaut */
 int i;

 i = 1;
 while (trie && i<=n-1)
 {
  if (tab[i-1]>tab[i])
  {
   trie = 0; /* faux */
  }
  i = i + 1;
 }

 return trie;
}

/*
  rechercheDichotomique:

   parametres d'entree :  - tab un tableau d'int
                          - n la taille du tableau
                          - e, la valeur a chercher
   parametres de sortie : - indice, l'endroit ou trouver un int pour
                            stocker l'indice de la valeur dans tab

   precondition: le tableau tab doit etre trie !

   Retourne 1 (vrai) si la valeur est presente dans le tableau
   Retourne 0 (faux) si la valeur n'est pas presente dans le tableau

 Remarque : le tableau tab ne doit pas etre forcemment trie
*/
int rechercheDichotomique(int tab[], int n, int e)
{
 int droite = n-1;
 int gauche = 0;
 int trouve = 0; /* faux au depart */

 if (!estTrie(tab,n))             /* Verification precondition */
 {
  printf("rechercheDichotomique: le tableau n'est pas trie...\n");
  exit(1);
 }

 while (!trouve && gauche<=droite)
 {
  int milieu = (gauche+droite)/2;

  if (tab[milieu] == e)
  {
   trouve  = 1;      /* vrai */
  }
  else
  {
   if (tab[milieu]<e)
   {
    gauche = milieu + 1;
   }
   else
   {
    droite = milieu -1;
   }
  }
 }

 return trouve;
}

int main(void)
{
 int tab[10]= {1,3,5,7,9,11,13,15,17,19};
 int taille = 10;
 int valeur;

 printf("Valeur a rechercher dans le tableau ? "); scanf("%d",&valeur);

 if (rechercheDichotomique(tab,taille,valeur))
 {
  printf("%d se trouve dans le tableau\n",valeur);
 }
 else
 {
  printf("%d ne se trouve pas dans le tableau\n",valeur);
 }

 return 0;
}