/* Recherche de la presence d'une valeur entiere */
/* dans un tableau d'entiers trie                */
/* par ordre croissant                           */
/* Methode dichotomique                          */

public class RecherchePresenceMethodeDichotomique {

///////////////////////////////////////////////////
  
/* Recherche dichotomique de la presence         */
/* d'un int dans un tableau de int trie          */
/* par ordre croissant                           */
/* Retour de true si présent, false sinon        */
/* v : Entier recherché                          */
/* t : Tableau d'entiers de recherche            */
/*     (trié par ordre croissant)                */

  static boolean estPresent(int v,int [] t) {
    boolean run = true;
    boolean trouve = false;
    int indi = 0;
    int indf = t.length-1;
    int indm;
    while ( run == true ) {
      if ( indf == indi ) {
        if ( t[indi] == v ) {
          trouve = true; }
        run = false; }
        else {
        if ( indf == indi+1 ) {
          if ( ( t[indi] == v ) || ( t[indf] == v ) ) {
            trouve = true; }
          run = false; }
          else {
          indm = (indi+indf)/2;
          if ( t[indm] == v ) {
            run = false;
            trouve = true; }
            else {
            if ( v < t[indm] ) {
              indf = indm-1; }
              else {
              indi = indm+1; } } } } }
    return trouve ;
  }
  
///////////////////////////////////////////////////
  
/* Fonction d'affichage des valeurs contenues    */
/* dans un tableau de int                        */
  
  static void affichageTableau(int [] t) {
    for ( int i = 0 ; i < t.length ; i++ ) {
      Ecran.formater("%4d",t[i]); }
  }

/* Fonction de creation d'un tableau de 10 int   */
/* initialise avec des valeurs croissantes       */
  
  static int [] initRandCroissant() {
    int [] t = new int[10];
    t[0] =(int) (Math.random()*3.0);
    for ( int i = 1 ; i < t.length ; i++ ) {
      t[i] = t[i-1] + (int) (Math.random()*3.0); }
    return t;
  }
  
/* Programme principal                           */

  public static void main(String [] args) {
    boolean present;
    int v;
    //int [] t;
    //t = initRandCroissant();
    int [] t = { 0,1,1,1,2,4,4,6,7,9 };
    affichageTableau(t);
    Ecran.sautDeLigne();
    Ecran.afficher("SVP, valeur à rechercher : ");
    v = Clavier.saisirInt();
    present = estPresent(v,t);
    Ecran.afficherln(v," present : ",present);
  }
}