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

import java.util.Date;
import java.util.Random;

public class Recherche {

/* Fonction de test si un tableau de int          */
/* est trié                                       */
  
  static boolean testTrie(int n,int [] t) {
    for ( int i = 0 ; i < n-1 ; i++ ) {
      if ( t[i+1] < t[i] )
        return false; }
    return true;
  }

/* Fonction de creation d'un tableau de int       */
/* initialise avec des valeurs croissantes        */
  
  static void initRandCroissant(int n,int [] t,Random r) {
    t[0] =(int) (r.nextDouble()*5.0);
    for ( int i = 1 ; i < n ; i++ ) {
      t[i] = t[i-1] + (int) (r.nextDouble()*5.0); }
  }

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static void initRandQuasiCroissantPC(int n,int [] t,int nb,Random r) {
    initRandCroissant(n,t,r);
    int i1;
    int i2;
    int aux;
    if ( nb != 0 )
      for ( int i = 0 ; i < nb ; i++ ) {
        i1 =(int) (r.nextDouble()*(n));
        i2 =(int) (r.nextDouble()*(n));
        aux = t[i1];
        t[i1] = t[i2];
        t[i2] = aux; }
  }

/* Fonction de creation d'un tableau de 10 int    */
/* initialise avec des valeurs croissantes        */
  
  static void initRandQuasiCroissantPV(int n,int [] t,int nb,Random r) {
    initRandCroissant(n,t,r);
    int i1;
    int i2;
    int aux;
    if ( nb != 0 )
      for ( int i = 0 ; i < nb ; i++ ) {
        i1 =(int) (r.nextDouble()*(n-1));
        i2 = i1+1+(int) (r.nextDouble()*(t.length/50));
        if ( i2 < t.length ) {
          aux = t[i1];
          t[i1] = t[i2];
          t[i2] = aux; } }
  }

/* Fonction de creation d'un tableau d'entiers    */
/* initialise avec des valeurs tirees au sort     */
/* entre 0 et 1000 inclus                         */
  
  static void initRand(int n,int [] t,Random r,double max) {
    for ( int i = 0 ; i < n ; i++ ) {
      t[i] =(int) (r.nextDouble()*max); }
  }
  
/* Fonction de recherche de la presence          */
/* d'une valeur entiere dans un tableau de int   */

  static boolean estPresent(int v,int n,int [] t) {
    boolean trouve = false;
    int i = 0;
    while ( ( trouve == false ) && ( i < n ) ) {
      if ( t[i] == v ) {
        trouve = true; }
        else {
        i++; } }
    return trouve;
  }
 
/* Recherche sequentielle de la presence         */
/* d'un int dans un tableau de int trie          */

  static boolean estPresentTableauTrieMethodeSequentielle(int v,int n,int [] t) {
    boolean run = true;
    boolean trouve = false;
    int i = 0;
    while ( ( run == true ) && ( i < n ) ) {
      if ( t[i] == v ) {
        run = false;
        trouve = true; }
        else {
          if ( t[i] > v ) {
          run = false; }
          else {
          i++; } } }
    return trouve;
  }

/* Recherche sequentielle de la presence         */
/* d'un int dans un tableau de int trie          */
/* Version optimisee                             */

  static boolean estPresentTableauTrieMethodeSequentielle2(int v,int n,int [] t) {
    int i = 0;
    while ( ( i != n ) && ( t[i] < v ) ) {
      i++; }
    return ( ( i < n ) && ( t[i] == v ) );
  }

/* Recherche dichotomique de la presence         */
/* d'un int dans un tableau de int trie          */

  static boolean estPresentTableauTrieMethodeDichotomique1(int v,int n,int [] t) {
    boolean stop = false;
    boolean trouve = false;
    int indi = 0;
    int indf = n-1;
    int indm;
    while ( stop == false ) {
      if ( indf == indi ) {
        if ( t[indi] == v ) {
          trouve = true; }
        stop = true; }
        else {
        if ( indf == indi+1 ) {
          if ( ( t[indi] == v ) || ( t[indf] == v ) ) {
            trouve = true; }
          stop = true; }
          else {
          indm = (indi+indf)/2;
          if ( t[indm] == v ) {
            stop = true;
            trouve = true; }
            else {
            if ( v < t[indm] ) {
              indf = indm-1; }
              else {
              indi = indm+1; } } } } }
    return trouve ;
  }

/* Recherche dichotomique de la presence         */
/* d'un int dans un tableau de int trie          */

  static boolean estPresentTableauTrieMethodeDichotomique2(int v,int n,int [] t) {
    boolean stop;
    boolean b;
    int indi;
    int indf;
    int indm;
    int valm;
    b = false;
    stop = false;
    indi = 0;
    indf = n-1;
    indm = (indi+indf)/2;
    valm = t[indm];
    while ( ( b == false ) && ( stop == false ) ) {
      if ( valm == v ) {
        b = true; }
        else {
        if ( indi >= indf ) {
          stop = true; }
          else {
          if ( v < valm ) {
            indf = indm-1; }
            else {
            indi = indm+1; }
          indm = (indi+indf)/2;
          valm = t[indm]; } } }
    return b ;
  }
  
/* 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.afficherln(t[i]," "); }
  }

  static int hasardBornes(int n,int [] t,Random r) {
    int bi = t[0];
    int bf = t[n-1];
    return (int) (bi+(bf-bi+1)*r.nextDouble());
  }
  
  static void testsRecherche(int temps,int ni,int nf,int inc) {
    Ecran.formater("%72s","Aléatoire");
    Ecran.formater("%62s","Trié méthode séquentielle brutale");
    Ecran.formater("%62s","Trié méthode séquentielle optimisée 1");
    Ecran.formater("%62s","Trié méthode séquentielle optimisée 2");
    Ecran.formater("%62s","Trié méthode dichotomique 1");
    Ecran.formater("%62s\n","Trié méthode dichotomique 2");
    Ecran.formater("%10s","Taille");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(n)");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(log(n))");
    Ecran.formater("%12s%14s%22s%14s",
                   "Appels","Temps total","Temps moyen",
                   "o(log(n))");
    Ecran.formater("\n");
    double max = 2000000000.0;
    int [] t = new int[100000000];
    Random r = new Random(0);
    for ( int n = ni ; n <= nf ; n = n+inc ) {
      Ecran.formater("%10d",n);
      { { r.setSeed(0);
          initRand(n,t,r,max);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            estPresent((int) (r.nextDouble()*max),n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          int v;
          long tiGen = System.nanoTime();
          for ( long j = 0L ; j < i ; j++ ) {
            v =(int) (r.nextDouble()*max); }
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n)); }
        r.setSeed(0);
        initRandCroissant(n,t,r);
        if ( !testTrie(n,t) ) {
          Ecran.afficher("Pas trié!!!!"); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            estPresent(hasardBornes(n,t,r),n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          int v;
          long tiGen = System.nanoTime();
          for ( long j = 0L ; j < i ; j++ ) {
            v = hasardBornes(n,t,r); }
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            estPresentTableauTrieMethodeSequentielle(hasardBornes(n,t,r),n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          int v;
          long tiGen = System.nanoTime();
          for ( long j = 0L ; j < i ; j++ ) {
            v = hasardBornes(n,t,r); }
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            estPresentTableauTrieMethodeSequentielle2(hasardBornes(n,t,r),n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          int v;
          long tiGen = System.nanoTime();
          for ( long j = 0L ; j < i ; j++ ) {
            v = hasardBornes(n,t,r); }
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/((double) n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            estPresentTableauTrieMethodeDichotomique1(hasardBornes(n,t,r),n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          int v;
          long tiGen = System.nanoTime();
          for ( long j = 0L ; j < i ; j++ ) {
            v = hasardBornes(n,t,r); }
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/Math.log((double) n)); }
        { r.setSeed(0);
          Utilitaires.Minuteur mntr = new Utilitaires.Minuteur();
          mntr.temps = temps*1000;
          mntr.lancement();
          long i = 0;
          long ti = System.nanoTime();
          do {
            estPresentTableauTrieMethodeDichotomique2(hasardBornes(n,t,r),n,t);
            i++; }
          while ( mntr.enCours );
          long tl = System.nanoTime()-ti;
          r.setSeed(0);
          int v;
          long tiGen = System.nanoTime();
          for ( long j = 0L ; j < i ; j++ ) {
            v = hasardBornes(n,t,r); }
          long tGen = System.nanoTime()-tiGen;
          tl -= tGen;
          Ecran.formater("%12d%14d%22.3f%14.4f",
                         i,tl,(double) tl/i,
                         ((double) tl/i)/Math.log((double) n)); }
        Ecran.formater("\n"); } }
  }
  
/* Programme principal                           */

  public static void main(String [] args) {
    //testsRecherche(30,2,2,1);
    //testsRecherche(30,2,100,1);
    testsRecherche(10,650,1000,1);
    testsRecherche(10,10,10000,10);
    testsRecherche(10,100,100000,100);
    testsRecherche(10,1000,250000,1000);
    testsRecherche(10,10000,1000000,10000);
    testsRecherche(10,50000,10000000,50000);
    testsRecherche(10,100000,100000000,100000);
  }
}