import java.util.*;

class DichoWords {

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

    /**
     * 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(String[] tab, int deb, int fin, String val) {
        int i = deb;
        int trouvé = -1;
        while (trouvé == -1 && i <= fin) {
            if (tab[i].equals(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(String[] tab, int deb, int fin, String val) {
        int trouvé;
        if (deb > fin) {
            trouvé = -1;
        } else {
            int milieu = (deb + fin) / 2;
            int cmp = val.compareTo(tab[milieu]);
            if (cmp == 0)
                trouvé = milieu;
            else if (cmp < 0)
                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(String[] tab, int deb, int fin, String val) {
        int trouvé = -1;
        int min = deb;
        int max = fin;
        while (trouvé == -1 && min <= max) {
            int milieu = (min + max) / 2;
            int cmp = val.compareTo(tab[milieu]);
            if (cmp == 0)
                trouvé = milieu;
            else if (cmp < 0)
                max = milieu - 1;
            else
                min = milieu + 1;
        }
        return trouvé;
    }

    /**
     * Afficher le tableau 'tab'.
     */
    static void afficher(String[] 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) {
        String file = args.length > 0 ? args[0] : "/usr/share/dict/words";

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

        String[] tab = Words.readWords(file);

        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);
        input.nextLine();

        System.out.println("Entrer les valeurs à rechercher " +
                           "(ctrl-d pour terminer)");
        System.out.print("? ");
        while (input.hasNextLine()) {
            String val = input.nextLine().trim();
            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("? ");
        }
    }
}