Programming assignment 5.

Implement a function to find the K elements of a given array that are closet to the median. (Hint: You

could modify Quick_Select to find the answer!)

1. Request the user to enter a positive integer, and call it n.

2. Generate n random integers between -100 to 100 and save them in a.

3. Print the generated array.

4. Request the user to enter a number between 1 to n, and call it K.

5. Find the median of the array. (Hint: can you use quick select? What is the time complexity in this step?)

6. Save the differences from the median (|a[i]-median|) in a new array and call it diff. (Note: The K closet

elements/numbers have the K smallest difference from the median. What is the time complexity in this

stage?)

7. Use diff to find the K numbers. (Hint: can you use quick select again? What is the time complexity in this

step?)

8. Shift the found K numbers back to their original value (+median). (Question: What is the time complexity

in this step?)

9. Print the answer ðŸ˜Š

10. Calculate the total time complexity of your algorithm and present your answer when demoing.