SHARE
TWEET

Untitled

a guest Nov 22nd, 2019 91 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.                 return find0(a, x, t - (int) Math.pow(2, numberOfSteps - 1), max, numberOfSteps + 1);
  36.             } else {
  37.                 return probalisticSearch0(a, x, min, t - (int) Math.pow(2, numberOfSteps - 1), numberOfSteps + 1);
  38.             }
  39.         }
  40. //        if(a[t] < x)
  41. //            return find0(a, x, t, max, numberOfSteps+1);
  42.         return new int[]{-1, numberOfSteps};
  43.     }
  44.  
  45.     private static int calculatePosition(int[] a, int x, int min, int max) {
  46.         int position;
  47.         double outcome, denominatorTop, denominatorBottom, numerator;
  48.  
  49.         numerator = x - a[min];
  50.         denominatorTop = a[max] - a[min];
  51.         denominatorBottom = max;
  52.  
  53.         outcome = (numerator / ((denominatorTop) / (denominatorBottom)));
  54.         position = (int) Math.round(outcome);
  55.  
  56.         return position;
  57.     }
  58.  
  59. //    public static int[] probalisticSearch(int[] arr, int value) {
  60. //        //int position = probSearch(arr, value);
  61. //        int steps = 1, a = 0;
  62. //
  63. //        if (arr[position] == value) {
  64. //            return new int[]{position, steps};
  65. //        }
  66. //        if (arr[position] > value) {
  67. //            for (int i = 0; i < arr.length; i++) {
  68. //                a = 2 ^ i;
  69. //                steps++;
  70. //                if (arr[position - a] == value) {
  71. //                    return new int[]{position - a, steps};
  72. //                } else if (arr[position - a] < value) {
  73. //
  74. //                }
  75. //            }
  76. //        }
  77. //        if (arr[position] < value) {
  78. //
  79. //        }
  80. //        return new int[]{};
  81. //    }
  82.  
  83.     public static void compareApproaches(int[] arr, int min, int max) {
  84.         // TODO
  85.     }
  86.  
  87.     public static void main(String[] args) {
  88.         // Not part of the exercise but can be helpful for debugging purposes
  89.         int[] exampleArray = new int[]{6, 20, 22, 35, 51, 54, 59, 74, 77, 80, 87, 94, 97};
  90.  
  91.         int[] result = probalisticSearch(exampleArray, 74);
  92.         write(result[0] + ", " + result[1]);
  93.     }
  94. }
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