import algds.IOUtils;

public class aufgabe20c {

    /* Hilfsmethode: Initialisierung eines Feldes */
    public static int[] init (int elemente)
    {
        int[]feld = new int[elemente];
        for (int i=0;i<elemente;i++)
        feld[i] = (int) (10+90*Math.random() );
        return feld;
    }


    /* Hilfsmethode: Ausgabe der Elemente eines Feldes */
    static void print (int[] feld) {
        for (int i = 0; i < feld.length; i++)
        System.out.print (feld[i] + " ");
        System.out.println ();
    }

    /*
     * Hilfsmethode: Austauch zweier Feldelemente
     */
    static void swap (int[] array, int idx1, int idx2) {
        int tmp = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = tmp;
    }

    // Implementierung des QuickSort
    // Hilfsmethode für rekursives Sortieren
    static void qsort (int[] feld, int l, int r) {
        int lo = l, hi = r;

        if (hi > lo) {
            // Pivotelement bestimmen
            int mid = feld[(lo + hi) / 2];


            while (lo <= hi) {
                // Erstes Element suchen, das größer oder gleich dem
                // Pivotelement ist, beginnend vom linken Index
                while ((lo < r) && (feld[lo] < mid))
                ++lo;

                // Element suchen, das kleiner oder gleich dem
                // Pivotelement ist, beginnend vom rechten Index
                while (( hi > l ) && ( feld[hi] > mid))
                --hi;

                // Wenn Indexe nicht gekreuzt --> Inhalte vertauschen
                if (lo <= hi) {
                    swap(feld, lo, hi);
                    ++lo;
                    --hi;
                }
            }

            // Linke Partition sortieren
            if (l < hi)
            qsort (feld, l, hi);

            // Rechte Partition sortieren
            if (lo < r)
            qsort( feld, lo, r);
        }
    }

    static void quickSort (int[] feld) {
        qsort (feld, 0, feld.length - 1);
    }

    /* Methode binSearch wie in 20b bis auf das der Suchwert nicht
    /* mit m sonder den Wert feld[m] also den Wert an der Stelle
    /* verglichen wird*/
    public static int binSearch (int feld[], int wert)
    {
        int l=0;
        int r=feld.length-1;
        while (l<=r) {
            int m = (l+r)/2;
            if ( wert < feld[m] )
            r = m-1;
            else if (wert > feld[m] )
            l = m+1;
            else
            return feld[m];
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int wert;
        int m;
        int[] feld = null;
        feld = init(20);
        System.out.print("Feld mit 20 zweistelligen Elementen  : ");
        print (feld);
        quickSort (feld);
        System.out.print("Feld mit Methode Quick-Sort sortiert : ");
        print (feld);
        System.out.print("Wert nach dem Sie suchen wollen bitte eingeben : ");
        wert=IOUtils.readInt();
        System.out.println (wert);
        if (binSearch(feld,wert)<=0)
        System.out.println("  "+wert+" NICHT gefunden ");
        else
        System.out.println("  "+wert+" gefunden");
    }
}