Now we check this position and go from this position in the required direction, whereby we proceed exponentially here, i.e. in the first step 2^0 in one direction we go 2^1 ... 2^n.
As soon as the program has to go once in the opposite direction (e.g.: our values were always too small up to now, but now they are suddenly too large) we have found an interval in which the searched value must lie. From this moment on we use the binary search as an auxiliary function.
The probabilistic search already has a step in the first attempt. And for each further step, the number of steps is increased. So, if the first Guess is one step away, the number of steps is 2. The binary search is called with the values min and max in such a way that the area is searched which has not yet been covered by the probabilistic search. As a parameter for the number of steps in the binary search, the previous step number +1 is passed.
Example:
int[] exampleArray = new int[]{6, 20, 22, 35, 51, 54, 59, 74, 77, 80, 87, 94, 97};
-> For 22 --> [2, 1]
-> For 74 --> [7, 3]
-> For 74 --> [-1, 3]
Implementation:
Your task is to implement a method public static int[] probalisticSearch(int[] arr, int value) that implements the algorithm described above. The passed array is always sorted. The searched value int value is always within the range between the smallest and largest value of the array.
The return array has at the first position (index 0) the index of the searched value in the array or -1 if the searched number does not appear in the array. In second place (index 1) your function returns how many calls it took to find the correct value or return that the value does not exist in the array.
Now we want to compare the performance of the two approaches. For this there is the slightly modified version of public static int[] find (int[] a, int x) in the template, which, like your method, first returns the index and then the required number of calls.
Write a method public static void compareApproaches(int[] arr, int min, int max), which searches all values (including min and max and no matter if the values in between are contained in the array or not) between min and max in the array with both variants and returns how many calls the variants needed.
In addition, your program should output what was the largest number of steps and at what value this occurred (if there are multiple values with the same number of values, they will output the first with that number).
Example:
Array: {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 100};
Index searching for is: 3
Probabilistic search: Position is: 1 number of Steps is: 1
Probabilistic search: Position is: 2 number of Steps is: 2
Probabilistic search: Position is: 4 number of Steps is: 3
Probabilistic search: Position is: 8 number of Steps is: 4
Probabilistic search: Position is: 16 number of Steps is: 5
Binary search: n1 is: 17 n2 is: 23 number of Steps is: 6
Binary search: n1 is: 21 n2 is: 23 number of Steps is: 7
Binary search: n1 is: 23 n2 is: 23 number of Steps is: 8
------------------------------------------
Index searching for is: 25
Probabilistic search: Position is: 6 number of Steps is: 1
Probabilistic search: Position is: 7 number of Steps is: 2
Probabilistic search: Position is: 9 number of Steps is: 3
Probabilistic search: Position is: 13 number of Steps is: 4
Probabilistic search: Position is: 21 number of Steps is: 5
Binary search: n1 is: 22 n2 is: 23 number of Steps is: 6
Binary search: n1 is: 23 n2 is: 23 number of Steps is: 7