Laboratory Test 2
In this exercise, you work with sorted arrays of integers with repetitions.
Part 1: Creating a random sorted array [25 points]
Read the array size n from the user, and prepare a random sorted array A of n positive integers. A[0] is a small integer (like a random value between 1 and 10). For i > 0, A[ i ] = A[ i - 1 ] with probability 1/2. Moreover, if A[ i ] > A[ i - 1 ], the difference A[ i ] - A[ i - 1 ] is 1, 2 or 3, each with probability 1/3. Print the array neatly.
Part 2: For students with odd PC numbers [45 points]
Write a function that, given A (and n) and a key x as input, returns the number of elements in A that are less than or equal to x.
Part 2: For students with even PC numbers [45 points]
Write a function that, given A (and n) and a key x as input, returns the index of the first occurrence of x in A. If x is not at all present in A, the function should return an invalid index like -1.
Note for Part 2
Your function must run in O(log n) time. If you write an O(n)-time algorithm, your Part 2 will be evaluated in 10. If t is the number of occurrences of x in A, and your function has a portion with running time proportional to t, your Part 2 will be evaluated in 20 (since t may be as large as n).
As a comment immediately before the function, explain the correctness of your algorithm.
Part 3 [30 points]
Invoking the function of Part 2 a constant number of times, efficiently determine how many times a key x occurs in A. Use the special structure of A described in Part 1. Do not call any other function. Each query for Part 3 must run in O(log n) time only.
Sample output
$ ./a.out n = 100 5 5 5 5 6 9 9 12 12 12 12 12 14 14 17 19 19 20 21 22 22 22 22 23 26 28 28 29 32 33 36 36 37 37 39 40 42 43 43 43 45 45 46 48 48 48 48 51 54 54 57 59 59 59 61 61 62 63 65 67 68 69 72 72 72 74 74 76 79 80 80 80 80 82 84 87 87 88 90 90 91 91 92 95 98 99 102 104 107 108 108 111 114 114 114 115 115 117 117 117 x = 48 *** For students with ODD PC numbers: Number of elements less than or equal to 48 is 47 Number of occurrences of 48 is 4 *** For students with EVEN PC numbers: Index of the first occurrence of 48 is 43 Number of occurrences of 48 is 4 x = 60 *** For students with ODD PC numbers: Number of elements less than or equal to 60 is 54 Number of occurrences of 60 is 0 *** For students with EVEN PC numbers: Index of the first occurrence of 60 is -1 Number of occurrences of 60 is 0 x = 0 $Submission site