gistfile1.txt

package pgdp.arrays;


public class ProbabilisticSearch extends  MiniJava {
    /**
     * Binary Search aus der Vorlesung leicht abgewandelt
     */

    public static int[] find (int[] a, int x) {
        return find0(a, x, 0, a.length-1, 1);
    }

    public static int[] find0 (int[] a, int x, int n1, int n2, int numberOfSteps) {
        int t = (n1+n2)/2;
        if (a[t] == x)
            return new int[]{t, numberOfSteps};
        else if (n1 >= n2)
            return new int[]{-1, numberOfSteps};
        else if (x > a[t])
            return find0 (a,x,t+1,n2, numberOfSteps + 1);
        else if (n1 < t)
            return find0 (a,x,n1,t-1, numberOfSteps + 1);
        else return new int[]{-1, numberOfSteps};
    }

    public static int[] probalisticSearch(int[] arr, int value) {
        if (arr == null) return new int[0];
        if (arr.length == 0) return new int[0];

        float exactPosition;
        int pos;
        float min = arr[0];
        float max = arr[0];

        // Determining the min and max element
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
            if (arr[i] < min) min = arr[i];
        }

        if (value < min || value > max) return new int[]{-1,1};

        // Probalistic formula
        exactPosition = (value - min) / ((max - min) / (arr.length));
        pos = Math.round(exactPosition);

        if (pos < 0 || pos > arr.length - 1) {
            return new int[]{-1, 0};
        }

        // In case we instantly found the value, we just return
        if (arr[pos] == value) {
            return new int[]{pos, 1};
        }

        // First case: Value is smaller than the current array position
        if (value < arr[pos])
            return mixedSearch(true, value, arr, pos);
        else
            return mixedSearch(false, value, arr, pos);
    }

    public static int[] mixedSearch(boolean left, int value, int[] arr, int pos) {
        if (arr == null) return new int[]{0,0};
        if (arr.length == 0) return new int[]{0,0};

        int moveBy = 1;
        int steps = 1;
        int prevPos;

        while (true) {
            prevPos = pos;
            steps++;

            if (left) {
                // Move to the left
                pos -= moveBy;

                // If the new position is bigger than value
                if (value < arr[pos]) {
                    moveBy *= 2;

                    // If we leave the array in the next iteration
                    if (pos - moveBy < 0) {
                        steps++;
                        int[] result = find0(arr, value, 0, pos - 1, steps);
                        return new int[]{result[0], result[1]};
                    }
                } else {
                    // Value order changed
                    int[] result = find0(arr, value, pos + 1, prevPos - 1, steps);
                    return new int[]{result[0], result[1]};
                }
            } else {
                pos += moveBy;

                if (value > arr[pos]) {
                    moveBy *= 2;
                    if (pos + moveBy > arr.length - 1) {
                        steps++;
                        return find0(arr, value, pos + 1, arr.length - 1, steps);
                    }
                } else {
                    int[] result = find0(arr, value, prevPos + 1, pos - 1, steps);
                    return new int[]{result[0], result[1]};
                }
            }
        }
    }

    public static void compareApproaches(int[] arr, int min, int max) {
        if (arr == null) return;
        if (arr.length == 0) return;

        /* Values > max or < min are counted as 1 step in the corresponding methods.
           Also I am not handling max < min, as stated by Johannes */

        int[] outProb;
        int[] outBin;

        int[] startProb = probalisticSearch(arr,min);
        int[] startBin = find(arr,min);

        int probMax = startProb[1];
        int binMax = startBin[1];

        int binIndex = min;
        int probIndex = min;

        long binTotal = 0;
        long probTotal = 0;

        for (int i = min; i <= max; i++) {
            // Save results of each iteration
            outProb = probalisticSearch(arr,i);
            outBin = find(arr, i);

            // Determine min & max tries
            if (outBin[1] > binMax) {
                 binMax = outBin[1];
                 binIndex = i;
            }

            if (outProb[1] > probMax) {
                probMax = outProb[1];
                probIndex = i;
            }

            // Sum up total tries
            binTotal += outBin[1];
            probTotal += outProb[1];
        }

        write("Binäre Suche:");
        write("Maximale Anzahl an Aufrufen:");
        write(binMax);

        write("Wert bei dem die maximale Anzahl an Aufrufen auftritt:");
        write(binIndex);

        write("Anzahl der gesamten Aufrufe:");
        write(binTotal);

        write("Probalistische Suche:");
        write("Maximale Anzahl an Aufrufen:");
        write(probMax);

        write("Wert bei dem die maximale Anzahl an Aufrufen auftritt:");
        write(probIndex);

        write("Anzahl der gesamten Aufrufe:");
        write(probTotal);
    }

    public static void main(String[] args) {
        // Not part of the exercise but can be helpful for debugging purposes
        int[] exampleArray1 = new int[]{6, 20, 22, 35, 51, 54, 59, 74, 77, 80, 87, 94, 97};
        int[] exampleArray2 = new int[]{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,100};
        compareApproaches(exampleArray3, -1000, 5000);
    }
 }