Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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) {
- return probalisticSearch0(arr, value, 0, arr.length - 1, 1);
- }
- public static int[] probalisticSearch0(int[] a, int x, int min, int max, int numberOfSteps) {
- int t = calculatePosition(a, x, min, max);
- if (a[t] == x)
- return new int[]{t, numberOfSteps};
- if (a[t] > x) {
- if (a[t - (int) Math.pow(2, numberOfSteps - 1)] < x) {
- if (a[t - (int) Math.pow(2, numberOfSteps - 1)+1] >= x)
- return find0(a, x, t - (int) Math.pow(2, numberOfSteps - 1), max, numberOfSteps + 1);
- else {
- numberOfSteps++;
- }
- } else {
- return probalisticSearch0(a, x, min, t - (int) Math.pow(2, numberOfSteps - 1), numberOfSteps + 1);
- }
- }
- // if(a[t] < x)
- // return find0(a, x, t, max, numberOfSteps+1);
- return new int[]{-1, numberOfSteps};
- }
- private static int calculatePosition(int[] a, int x, int min, int max) {
- int position;
- double outcome, denominatorTop, denominatorBottom, numerator;
- numerator = x - a[min];
- denominatorTop = a[max] - a[min];
- denominatorBottom = max;
- outcome = (numerator / ((denominatorTop) / (denominatorBottom)));
- position = (int) Math.round(outcome);
- return position;
- }
- // public static int[] probalisticSearch(int[] arr, int value) {
- // //int position = probSearch(arr, value);
- // int steps = 1, a = 0;
- //
- // if (arr[position] == value) {
- // return new int[]{position, steps};
- // }
- // if (arr[position] > value) {
- // for (int i = 0; i < arr.length; i++) {
- // a = 2 ^ i;
- // steps++;
- // if (arr[position - a] == value) {
- // return new int[]{position - a, steps};
- // } else if (arr[position - a] < value) {
- //
- // }
- // }
- // }
- // if (arr[position] < value) {
- //
- // }
- // return new int[]{};
- // }
- public static void compareApproaches(int[] arr, int min, int max) {
- // TODO
- }
- public static void main(String[] args) {
- // Not part of the exercise but can be helpful for debugging purposes
- int[] exampleArray = new int[]{6, 20, 22, 35, 51, 54, 59, 74, 77, 80, 87, 94, 97};
- int[] result = probalisticSearch(exampleArray, 22);
- write(result[0] + ", " + result[1]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement