import algds.IOUtils;
public class aufgabe20b {

    /* Initialisierung eines Feldes als Methode definiert */
    public static int[]init(int elemente)
    {
        int[]feld = new int[elemente];
        int i;
        for (i=0;i<elemente;i++){
            feld[i]=i+1;
        System.out.print(i+"  ");} //Ausgabe des feldes
        System.out.println();
        return feld;
    }
    // Methode binäres Suchen
    /* Zuerst wird eine linke und eine rechte Grenze
    /* definiert (linke = 0 , rechte = Länge des Feldes-1 )
    /* zuerst wird das mittlere Element betrachtet
    /* falls der Suchwert kleiner als m sein sollte
    /* wird die rechte Grenze auf m-1 gesetzt, weil sich der Suchwert
    /* nur in der linken Hälfte sein kann
    /* diese Hälfte wird analog durchsucht bis Abbruch
    /* falls der Suchwert größer als m sein sollte
    /* wird anlaog dazu die linke Grenze hochgesetzt*/
    public static int binSearch (int feld[], int wert)
    {
        int l = 0;
        int r=feld.length-1;
        while (l<=r)
        {
            int m = (l+r)/2;
            /* Zur Veranschaulichung werden in jedem Schleifendurchlauf
            /* die Werte für die Grenzen und die Mitte sowie die Position
            /* der Mitte ausgegeben*/
            System.out.println(" l : "+l+" m : "+m+" r : "+r);
            if ( wert < m )
            r = m-1;
            else
            if (wert > m )
            l = m+1;
            else
            return feld[m];  //Rückgabe der Position von m wenn wert=m
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int elemente;
        int wert;
        int m;
        int[] feld = null;
        System.out.print("Wieviel Elemente soll die Folge haben : ");
        elemente=IOUtils.readInt();
        System.out.println(elemente);
        feld = init(elemente);
        System.out.print("Wert nach dem sie suchen wollen : ");
        wert=IOUtils.readInt();
        System.out.println (wert);
        System.out.println("Element : "+wert+" liegt an der : "+(binSearch(feld,wert))+" Position ");
    }
}