## 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

nfrom the user, and prepare a random sorted arrayAofnpositive integers.A[0] is a small integer (like a random value between 1 and 10). Fori> 0,A[i] =A[i- 1 ] with probability 1/2. Moreover, ifA[i] >A[i- 1 ], the differenceA[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(andn) and a keyxas input, returns the number of elements inAthat are less than or equal tox.## Part 2: For students with even PC numbers [45 points]

Write a function that, given

A(andn) and a keyxas input, returns the index of thefirstoccurrence ofxinA. Ifxis not at all present inA, 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. Iftis the number of occurrences ofxinA, and your function has a portion with running time proportional tot, your Part 2 will be evaluated in 20 (sincetmay be as large asn).

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

xoccurs inA. Use the special structure ofAdescribed in Part 1. Do not call any other function. Each query for Part 3 must run in O(logn) 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