/*
 * Dieser Quelltext wurde von ChatGPT erstellt, auf der Grundlage
 * der vier Suchalgorithmen, die ich zuvor selbst erstellt habe.
 * 
 * Der Auftrag an ChatGPT bestand darin, aus den vier Methoden von mir
 * eine große Klasse zu erstellen, in denen die Zahl der Vergleiche
 * fuer die vier Methoden und fuer 64, 128, ... 2048 Zahlen ermittelt
 * und tabellarisch mit printf() ausgegeben wird.
 */

public class VergleicheSuchverfahren
{
    private static final int MIN_WERT = 1;
    private static final int MAX_WERT = 5000;

    public static void main(String[] args)
    {
        int[] groessen = {64, 128, 256, 512, 1024, 2048};

        System.out.println("Vergleich von vier Suchverfahren");
        System.out.println("Suchanfragen: alle Zahlen von 1 bis 5000");
        System.out.println();

        System.out.printf("%8s %21s %21s %21s %21s%n",
                          "n",
                          "Sprungsuche",
                          "Indexsuche",
                          "Interpolation",
                          "Binaersuche");
        System.out.printf("%8s %21s %218s %21s %21s%n",
                          "",
                          "(gesamt / mittel)",
                          "(gesamt / mittel)",
                          "(gesamt / mittel)",
                          "(gesamt / mittel)");
        System.out.println("----------------------------------------------------------------------------------------------------");

        for (int n : groessen)
        {
            int[] array = erzeugeSortiertesArray(n, MIN_WERT, MAX_WERT);
            int[] hilfsArray = hilfsArrayErzeugen(array);

            long summeSprung = 0;
            long summeIndex = 0;
            long summeInterpolation = 0;
            long summeBinaer = 0;

            for (int suchzahl = MIN_WERT; suchzahl <= MAX_WERT; suchzahl++)
            {
                summeSprung += sprungsucheVergleiche(array, suchzahl);
                summeIndex += indexsucheVergleiche(array, hilfsArray, suchzahl);
                summeInterpolation += interpolationssucheVergleiche(array, suchzahl);
                summeBinaer += binaersucheVergleiche(array, suchzahl);
            }

            double mittelSprung = (double) summeSprung / MAX_WERT;
            double mittelIndex = (double) summeIndex / MAX_WERT;
            double mittelInterpolation = (double) summeInterpolation / MAX_WERT;
            double mittelBinaer = (double) summeBinaer / MAX_WERT;

            System.out.printf("%8d %10d / %6.2f %10d / %6.2f %10d / %6.2f %10d / %6.2f%n",
                              n,
                              summeSprung, mittelSprung,
                              summeIndex, mittelIndex,
                              summeInterpolation, mittelInterpolation,
                              summeBinaer, mittelBinaer);
        }
    }

    /*
     * ------------------------------------------------------------------------
     * Erzeugt ein aufsteigend sortiertes Array mit n Werten zwischen min und max.
     * Die Werte sind moeglichst gleichmaessig ueber den Bereich verteilt.
     * ------------------------------------------------------------------------
     */

    private static int[] erzeugeSortiertesArray(int n, int min, int max)
    {
        int[] a = new int[n];

        if (n == 1)
        {
            a[0] = (min + max) / 2;
            return a;
        }

        for (int i = 0; i < n; i++)
        {
            a[i] = min + i * (max - min) / (n - 1);
        }

        return a;
    }

    /*
     * ------------------------------------------------------------------------
     * Hilfs-Array fuer die Indexsuche
     * ------------------------------------------------------------------------
     *
     * Das Hilfs-Array besitzt 11 Eintraege fuer 10 grobe Wertebereiche.
     */

    private static int[] hilfsArrayErzeugen(int[] hauptArray)
    {
        int[] hilfs = new int[11];

        hilfs[0] = 0;
        hilfs[hilfs.length - 1] = hauptArray.length - 1;

        int min = hauptArray[0];
        int max = hauptArray[hauptArray.length - 1];

        for (int j = 1; j < hilfs.length - 1; j++)
        {
            double grenze = min + j * (max - min) / 10.0;
            int i = 0;

            while (i < hauptArray.length - 1 && hauptArray[i] < grenze)
            {
                i++;
            }

            hilfs[j] = i;
        }

        return hilfs;
    }

    /*
     * ------------------------------------------------------------------------
     * Sprungsuche
     * ------------------------------------------------------------------------
     *
     * Rueckgabe: Anzahl der benoetigten Vergleiche
     */

    private static int sprungsucheVergleiche(int[] a, int suchzahl)
    {
        int vergleiche = 0;

        if (a == null || a.length == 0)
            return 0;

        vergleiche++;
        if (suchzahl < a[0])
            return vergleiche;

        vergleiche++;
        if (suchzahl > a[a.length - 1])
            return vergleiche;

        int sprungweite = (int) Math.sqrt(a.length);
        if (sprungweite < 1)
            sprungweite = 1;

        int i = 0;

        while (i < a.length)
        {
            vergleiche++;
            if (a[i] < suchzahl)
                i = i + sprungweite;
            else
                break;
        }

        int start = i - sprungweite;
        if (start < 0)
            start = 0;

        int ende = i;
        if (ende >= a.length)
            ende = a.length - 1;

        for (int k = start; k <= ende; k++)
        {
            vergleiche++;
            if (a[k] == suchzahl)
                return vergleiche;

            vergleiche++;
            if (a[k] > suchzahl)
                return vergleiche;
        }

        return vergleiche;
    }

    /*
     * ------------------------------------------------------------------------
     * Indexsuche
     * ------------------------------------------------------------------------
     *
     * Rueckgabe: Anzahl der benoetigten Vergleiche
     */

    private static int indexsucheVergleiche(int[] a, int[] hilfsArray, int suchzahl)
    {
        int vergleiche = 0;

        if (a == null || a.length == 0)
            return 0;

        vergleiche++;
        if (suchzahl < a[0])
            return vergleiche;

        vergleiche++;
        if (suchzahl > a[a.length - 1])
            return vergleiche;

        int i = 1;

        while (i < hilfsArray.length)
        {
            vergleiche++;
            if (suchzahl > a[hilfsArray[i]])
                i++;
            else
                break;
        }

        if (i >= hilfsArray.length)
            i = hilfsArray.length - 1;

        int start = hilfsArray[i - 1];
        int ende = hilfsArray[i];

        for (int j = start; j <= ende; j++)
        {
            vergleiche++;
            if (a[j] == suchzahl)
                return vergleiche;

            vergleiche++;
            if (a[j] > suchzahl)
                return vergleiche;
        }

        return vergleiche;
    }

    /*
     * ------------------------------------------------------------------------
     * Interpolationssuche
     * ------------------------------------------------------------------------
     *
     * Rueckgabe: Anzahl der benoetigten Vergleiche
     */

    private static int interpolationssucheVergleiche(int[] a, int suchzahl)
    {
        int vergleiche = 0;

        if (a == null || a.length == 0)
            return 0;

        vergleiche++;
        if (suchzahl < a[0])
            return vergleiche;

        vergleiche++;
        if (suchzahl > a[a.length - 1])
            return vergleiche;

        if (a.length == 1)
        {
            vergleiche++;
            return vergleiche;
        }

        int minimum = a[0];
        int maximum = a[a.length - 1];
        int spannweite = maximum - minimum;

        int intervalle = a.length - 1;
        double inkrement = (double) spannweite / intervalle;
        int wIndex = (int) ((suchzahl - minimum) / inkrement);

        if (wIndex < 0)
            wIndex = 0;

        if (wIndex > a.length - 1)
            wIndex = a.length - 1;

        vergleiche++;
        if (suchzahl == a[wIndex])
            return vergleiche;

        vergleiche++;
        if (suchzahl < a[wIndex])
        {
            for (int i = wIndex - 1; i >= 0; i--)
            {
                vergleiche++;
                if (a[i] == suchzahl)
                    return vergleiche;

                vergleiche++;
                if (a[i] < suchzahl)
                    return vergleiche;
            }
        }
        else
        {
            for (int i = wIndex + 1; i < a.length; i++)
            {
                vergleiche++;
                if (a[i] == suchzahl)
                    return vergleiche;

                vergleiche++;
                if (a[i] > suchzahl)
                    return vergleiche;
            }
        }

        return vergleiche;
    }

    /*
     * ------------------------------------------------------------------------
     * Binaersuche
     * ------------------------------------------------------------------------
     *
     * Rueckgabe: Anzahl der benoetigten Vergleiche
     */

    private static int binaersucheVergleiche(int[] a, int suchzahl)
    {
        int vergleiche = 0;

        if (a == null || a.length == 0)
            return 0;

        int links = 0;
        int rechts = a.length - 1;

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

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

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

        return vergleiche;
    }
}