#include <iostream>
using namespace std;

/**
    Test si un tableau t[0 à n] est ordonné (croissant)
*/
bool TableauOrdonne(int t[], int n)
{
    int i;
    for(i=1; i<=n; i++)
        if(t[i-1] >= t[i])
            return false;
    return true;
}


/**
    Test si un entier x appartient à un tableau t[0 à n], si le tableau est ordonné on utilise la dichotomie
*/
bool AppartTableau(int t[], int n, int x)
{
    bool ordonne = TableauOrdonne(t,n);
    int i;
    //par dichotomie :
    int debut = 0; int fin = n;
    int millieu;
    bool trouve = false;

    if(!ordonne)
    {
      for(i=0;i<=n;i++)
        if(x == t[i])
            return true;
      return false;
    }
    else  //tableau ordonné donc dichotomie :
    {
      do
      {
          millieu = int((debut+fin)/2);
          if(t[millieu] == x)
            return true;
          else if(x > t[millieu])
            debut = millieu + 1;
          else
            fin = millieu - 1;
      }
      while(trouve == false && debut <= fin);
      return false;
    }
}

/**
    Affiche toutes les valeurs d'un tableau : t[0 à n]
*/
void AfficheTableau(int t[], int n)
{
    int i;
    cout << "[";
    for(i=0; i<n; i++)
        cout << t[i]<< " , ";
    cout << "]" << endl;
}