## 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, Ai ] = Ai - 1 ] with probability 1/2. Moreover, if Ai ] > Ai - 1 ], the difference Ai ] - Ai - 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
\$
```