SHARE
TWEET

Untitled

a guest Nov 22nd, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package pgdp.arrays;
  2.  
  3. public class ProbabilisticSearch extends MiniJava {
  4.     /**
  5.      * Binary Search aus der Vorlesung leicht abgewandelt
  6.      */
  7.     public static int[] find(int[] a, int x) {
  8.         return find0(a, x, 0, a.length - 1, 1);
  9.     }
  10.  
  11.     public static int[] find0(int[] a, int x, int n1, int n2, int numberOfSteps) {
  12.         int t = (n1 + n2) / 2;
  13.         if (a[t] == x)
  14.             return new int[]{t, numberOfSteps};
  15.         else if (n1 >= n2)
  16.             return new int[]{-1, numberOfSteps};
  17.         else if (x > a[t])
  18.             return find0(a, x, t + 1, n2, numberOfSteps + 1);
  19.         else if (n1 < t)
  20.             return find0(a, x, n1, t - 1, numberOfSteps + 1);
  21.         else return new int[]{-1, numberOfSteps};
  22.     }
  23.  
  24.     public static int[] probalisticSearch(int[] arr, int value) {
  25.         return probalisticSearch0(arr, value, 0, arr.length - 1, 1);
  26.     }
  27.  
  28.     public static int[] probalisticSearch0(int[] a, int x, int min, int max, int numberOfSteps) {
  29.         int t = calculatePosition(a, x, min, max);
  30.  
  31.         if (a[t] == x)
  32.             return new int[]{t, numberOfSteps};
  33.         if (a[t] > x) {
  34.             if (a[t - (int) Math.pow(2, numberOfSteps - 1)] < x) {
  35.                 if (a[t - (int) Math.pow(2, numberOfSteps - 1)+1] >= x)
  36.                     return find0(a, x, t - (int) Math.pow(2, numberOfSteps - 1), max, numberOfSteps + 1);
  37.                 else {
  38.                     numberOfSteps++;
  39.                 }
  40.             } else {
  41.                 return probalisticSearch0(a, x, min, t - (int) Math.pow(2, numberOfSteps - 1), numberOfSteps + 1);
  42.             }
  43.         }
  44. //        if(a[t] < x)
  45. //            return find0(a, x, t, max, numberOfSteps+1);
  46.         return new int[]{-1, numberOfSteps};
  47.     }
  48.  
  49.     private static int calculatePosition(int[] a, int x, int min, int max) {
  50.         int position;
  51.         double outcome, denominatorTop, denominatorBottom, numerator;
  52.  
  53.         numerator = x - a[min];
  54.         denominatorTop = a[max] - a[min];
  55.         denominatorBottom = max;
  56.  
  57.         outcome = (numerator / ((denominatorTop) / (denominatorBottom)));
  58.         position = (int) Math.round(outcome);
  59.  
  60.         return position;
  61.     }
  62.  
  63. //    public static int[] probalisticSearch(int[] arr, int value) {
  64. //        //int position = probSearch(arr, value);
  65. //        int steps = 1, a = 0;
  66. //
  67. //        if (arr[position] == value) {
  68. //            return new int[]{position, steps};
  69. //        }
  70. //        if (arr[position] > value) {
  71. //            for (int i = 0; i < arr.length; i++) {
  72. //                a = 2 ^ i;
  73. //                steps++;
  74. //                if (arr[position - a] == value) {
  75. //                    return new int[]{position - a, steps};
  76. //                } else if (arr[position - a] < value) {
  77. //
  78. //                }
  79. //            }
  80. //        }
  81. //        if (arr[position] < value) {
  82. //
  83. //        }
  84. //        return new int[]{};
  85. //    }
  86.  
  87.     public static void compareApproaches(int[] arr, int min, int max) {
  88.         // TODO
  89.     }
  90.  
  91.     public static void main(String[] args) {
  92.         // Not part of the exercise but can be helpful for debugging purposes
  93.         int[] exampleArray = new int[]{6, 20, 22, 35, 51, 54, 59, 74, 77, 80, 87, 94, 97};
  94.  
  95.         int[] result = probalisticSearch(exampleArray, 22);
  96.         write(result[0] + ", " + result[1]);
  97.     }
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top