/* 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 TestVitesseRechercheGlobal {

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

  static boolean estPresentMethodeSequentielle(int v,int [] t) {
    boolean b;
    int i;
    b = false;
    i = 0;
    while ( ( i < t.length ) && ( v >= t[i] ) ) {
      b = (t[i] == v);
      i++; }
    return b ;
  }

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

  static boolean estPresentMethodeDichotomique(int v,int [] t) {
    boolean stop;
    boolean b;
    int indi;
    int indf;
    int indm;
    int valm;
    b = false;
    stop = false;
    indi = 0;
    indf = t.length-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]," "); }
  }

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

  public static void main(String [] args) {
    boolean present;
    int [] t;
    int v;
    int n;
    long nb;
    int cpt;
    long ts;
    long td;
    for ( n = 10 ; n <= 100000000 ; ) {
    //double fact = Math.log(n)*1.442695; 
    //nb =(long) (2000000000L/fact);
    nb = (50000000000L/n);
    //for ( nb = 10000000 ; nb <= 10000000 ; ) {
    Ecran.afficher(n," ",nb," ");
    t = initRandCroissant(n);
    { Date di = new Date();
      cpt = 0;
      Random rd = new Random(1);
      for ( int i = 0 ; i < nb ; i++ ) {
        v =(int) ((t[t.length-1]+1)*rd.nextDouble());
        present = estPresentMethodeSequentielle(v,t);
        if ( present )
          cpt++; }
      Date df = new Date();
      Ecran.afficher(ts = df.getTime()-di.getTime()," "); }
  /*  { Date di = new Date();
      cpt = 0;
      Random rd = new Random(1);
      for ( int i = 0 ; i < nb ; i++ ) {
        v =(int) ((t[t.length-1]+1)*rd.nextDouble());
        present = estPresentMethodeDichotomique(v,t);
        if ( present )
          cpt++; }
      Date df = new Date();
      Ecran.afficher(td = df.getTime()-di.getTime()," "); }*/
    //Ecran.afficherln((double) ts/td);
    Ecran.afficherln();
    //nb = next(nb); }
    n = next(n); }
  }
  
  static int next(int n) {
    switch (n) {
      case 10        : return(20);
      case 20        : return(50);
      case 50        : return(100);
      case 100       : return(200);
      case 200       : return(500);
      case 500       : return(1000);
      case 1000      : return(2000);
      case 2000      : return(5000);
      case 5000      : return(10000);
      case 10000     : return(20000);
      case 20000     : return(50000);
      case 50000     : return(100000);
      case 100000    : return(200000);
      case 200000    : return(500000);
      case 500000    : return(1000000);
      case 1000000   : return(2000000);
      case 2000000   : return(5000000);
      case 5000000   : return(10000000);
      case 10000000  : return(20000000);
      case 20000000  : return(50000000);
      case 50000000  : return(100000000);
      case 100000000 : return(200000000);
      case 200000000 : return(500000000);
      case 500000000 : return(1000000000); }
    return(1000000000);
  }
}