import java.util.*;

class Dicho {

    /**
     * Différence maximale entre deux valeurs successives dans le tableau
     * (cf. fonction remplir).
     */
    static final int INCR = 10;

    static final Scanner input = new Scanner(System.in);
    static final Random random = new Random();

    /**
     * Renvoie l'indice de 'val' dans 'tab' entre les indices 'deb' et 'fin' si
     * elle y est, ou -1 sinon.
     * (recherche simple)
     */
    static int rechSimple(int[] tab, int deb, int fin, int val) {
        int i = deb;
        int trouvé = -1;
        while (trouvé == -1 && i <= fin) {
            if (tab[i] == val)
                trouvé = i;
            i++;
        }
        return trouvé;
    }

    /**
     * Renvoie l'indice de 'val' dans 'tab' entre les indices 'deb' et 'fin' si
     * elle y est, ou -1 sinon.
     * (recherche dichotomique récursive)
     */
    static int rechDichoRec(int[] tab, int deb, int fin, int val) {
        int trouvé;
        if (deb > fin) {
            trouvé = -1;
        } else {
            int milieu = (deb + fin) / 2;
            if (tab[milieu] == val)
                trouvé = milieu;
            else if (val < tab[milieu])
                trouvé = rechDichoRec(tab, deb, milieu - 1, val);
            else
                trouvé = rechDichoRec(tab, milieu + 1, fin, val);
        }
        return trouvé;
    }

    /**
     * Renvoie l'indice de 'val' dans 'tab' entre les indices 'deb' et 'fin' si
     * elle y est, ou -1 sinon.
     * (recherche dichotomique itérative)
     */
    static int rechDichoIter(int[] tab, int deb, int fin, int val) {
        int trouvé = -1;
        int min = deb;
        int max = fin;
        while (trouvé == -1 && min <= max) {
            int milieu = (min + max) / 2;
            if (tab[milieu] == val)
                trouvé = milieu;
            else if (val < tab[milieu])
                max = milieu - 1;
            else
                min = milieu + 1;
        }
        return trouvé;
    }

    /**
     * Remplit le tableau 'tab' avec des valeurs croissantes.
     */
    static void remplir(int[] tab) {
        int val = 0;
        for (int i = 0; i < tab.length; i++) {
            int incr = INCR;
            if (Integer.MAX_VALUE - val < incr)
                incr = Integer.MAX_VALUE - val;
            val += random.nextInt(incr + 1);
            tab[i] = val;
        }
    }

    /**
     * Afficher le tableau 'tab'.
     */
    static void afficher(int[] tab) {
        System.out.print("[");
        if (tab.length > 0)
            System.out.print(" " + tab[0]);
        for (int i = 1; i < tab.length; i++)
            System.out.print(", " + tab[i]);
        System.out.println(" ]");
    }

    public static void main(String[] args) {
        System.out.print("Taille du tableau ? ");
        int taille = input.nextInt();

        System.out.print("Génération... ");
        System.out.flush();

        int[] tab = new int[taille];
        remplir(tab);

        System.out.print("len = " + tab.length);
        if (tab.length > 0)
            System.out.print(", min = " + tab[0] +
                             ", max = " + tab[tab.length - 1]);
        System.out.println();

        System.out.print("Affichage du tableau (o/n) ? ");
        if (input.next().charAt(0) == 'o')
            afficher(tab);

        System.out.println("Entrer les valeurs à rechercher " +
                           "(ctrl-d pour terminer)");
        System.out.print("? ");
        while (input.hasNextInt()) {
            int val = input.nextInt();
            int res;
            long t0, t1;

            t0 = System.nanoTime();
            res = rechSimple(tab, 0, tab.length - 1, val);
            t1 = System.nanoTime();
            System.out.println("recherche simple       : " + res +
                               ", durée = " + ((t1 - t0) * 1e-6) + " ms");
            if (res != -1)
                System.out.println("\ttab[" + res + "] = " + tab[res]);

            t0 = System.nanoTime();
            res = rechDichoRec(tab, 0, tab.length - 1, val);
            t1 = System.nanoTime();
            System.out.println("recherche dicho. réc.  : " + res +
                               ", durée = " + ((t1 - t0) * 1e-6) + " ms");
            if (res != -1)
                System.out.println("\ttab[" + res + "] = " + tab[res]);

            t0 = System.nanoTime();
            res = rechDichoIter(tab, 0, tab.length - 1, val);
            t1 = System.nanoTime();
            System.out.println("recherche dicho. itér. : " + res +
                               ", durée = " + ((t1 - t0) * 1e-6) + " ms");
            if (res != -1)
                System.out.println("\ttab[" + res + "] = " + tab[res]);

            System.out.print("? ");
        }
    }
}