public class VergleichBinSeq
{
    public VergleichBinSeq()
    {
        ermittleSuchzeit(   64);
        ermittleSuchzeit(  128);      
        ermittleSuchzeit(  256);        
        ermittleSuchzeit(  512);      
        ermittleSuchzeit( 1024);        
        ermittleSuchzeit( 2048);    
        ermittleSuchzeit( 4096);        
    }

    /*
     * ------------------------------------------------------------------------
     * Hier der Algorithmus zur modifizierten binären Suche, wie er in der 
     * Präsentation und im Skript gezeigt wird.
     * ------------------------------------------------------------------------
     */

    public int vergleicheBinaer(int[] a, int suchzahl)
    {
        int links = 0;
        int rechts = a.length - 1;
        int v = 0;

        while (links <= rechts)
        {
            int mitte = (links + rechts) / 2;

            v++; 
            if (a[mitte] == suchzahl) return v;

            v++;
            if (suchzahl < a[mitte])
                rechts = mitte - 1;
            else
                links = mitte + 1;
        }

        return v;
    }


    /*
     * ------------------------------------------------------------------------
     * Und hier der Algorithmus zur modifizierten linearen Suche, wie er in der 
     * Präsentation und im Skript gezeigt wird.
     * ------------------------------------------------------------------------
     */    

    public int vergleicheLinear(int[] a, int suchzahl)
    {
        int v = 0;

        for (int i = 0; i < a.length; i++)
        {
            v++;
            if (a[i] == suchzahl)
            {
                return v;
            }
        }

        return v;
    }    

    /*
     * ------------------------------------------------------------------------
     * Testmethode für diesen Algorithmus
     * ------------------------------------------------------------------------
     */

    public void ermittleSuchzeit(int arraygroesse)
    {
        int[] zahlen = new int[arraygroesse];

        int vergleicheB = 0;
        int vergleicheL = 0;

        for (int i=0; i < zahlen.length; i++)
            zahlen[i] = i*2;

        for (int suchzahl=1; suchzahl<=arraygroesse; suchzahl++)
        {
            vergleicheB += vergleicheBinaer(zahlen,suchzahl);   
            vergleicheL += vergleicheLinear(zahlen,suchzahl);   
        }   

        System.out.println("Lineare Suche für " + arraygroesse + " Zahlen = " + vergleicheL + " Vergleiche");
        System.out.println("Binaere Suche für " + arraygroesse + " Zahlen = " + vergleicheB + " Vergleiche");

        double verh = (double) vergleicheL/vergleicheB;
        System.out.printf("Verhältnis Linear/Binär = %12.2f %n%n",verh);
    }

    public static void main(String[] args)
    {
        new VergleichBinSeq();
    }    

}