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

/* 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++ ) {
      Console.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) {
    Console.setTitle("TestVitesseRecherche");
    boolean present;
    int [] t;
    int v;
    int n;
    long nb;
    long cpt;
    long cpt2;
    Console.afficher("SVP, taille du tableau    : ");
    n = Console.saisirInt();
    t = initRandCroissant(n);
    Console.afficher("SVP, nombre de recherches : ");
    nb = Console.saisirLong();
    Console.formater("Temps        :        Total      Gestion     Effectif\n");
    for ( int i = 0 ; i < 10000000 ; i++ ) {
      v =(int) ((t[t.length-1]+1)*Math.random()); }
    { cpt = 0;
      Random rd = new Random(1);
      long ti = System.nanoTime();
      for ( int i = 0 ; i < nb ; i++ ) {
        v =(int) ((t[t.length-1]+1)*rd.nextDouble());
        if ( estPresentMethodeSequentielle(v,t) )
          cpt++; }
      long tf = System.nanoTime();
      cpt2 = cpt;
      cpt = 0;
      rd.setSeed(1);
      long ti2 = System.nanoTime();
      for ( long i = 0 ; i < nb ; i++ ) {
        v =(int) ((t[t.length-1]+1)*rd.nextDouble());
        if ( i < cpt2 ) {
          cpt++; } }
      long tf2 = System.nanoTime();
      Console.formater("Séquentiel   :%13d%13d%13d ns\n",tf-ti,tf2-ti2,tf-ti-(tf2-ti2)); }
    { cpt = 0;
      Random rd = new Random(1);
      long ti = System.nanoTime();
      for ( int i = 0 ; i < nb ; i++ ) {
        v =(int) ((t[t.length-1]+1)*rd.nextDouble());
        if ( estPresentMethodeDichotomique(v,t) )
          cpt++; }
      long tf = System.nanoTime();
      cpt2 = cpt;
      cpt = 0;
      rd.setSeed(1);
      long ti2 = System.nanoTime();
      for ( long i = 0 ; i < nb ; i++ ) {
        v =(int) ((t[t.length-1]+1)*rd.nextDouble());
        if ( i < cpt2 ) {
          cpt++; } }
      long tf2 = System.nanoTime();
      Console.formater("Dichotomique :%13d%13d%13d ns\n",tf-ti,tf2-ti2,tf-ti-(tf2-ti2)); }
  }
}