PROGRAMMING:Find the kth smallest number
Design an algorithm with an average time of O (n) to find the kth smallest number among n (1 < = n < = 1000) unordered integers.
Tip: the function of int partition (int a [], int left, int right) is to divide a [left] ~ a [right] according to an element X (such as a [left]) in a [left] ~ a [right]. After the division, the left segment of X is less than or equal to x, and the right segment is greater than or equal to X. at the same time, the position of X can be used to calculate the number of X in ascending non descending order of this batch of data. Therefore, we can program int find (int a [], int left, int right, int k) function, obtain the partition point by calling the partition function, and judge whether the partition point is the kth smallest. If not, recursively call find function to continue to search in the left or right segment.
###Input format:
There are two lines of input:
The first line is n and K, 0 < K < = n < = 10000
The second line is n integers
###Output format:
Output the kth smallest number
###Input example:
Here is a set of inputs. For example:
```in
10 4
2 8 9 0 1 3 6 7 8 2
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
answer：If there is no answer, please comment
Tip: the function of int partition (int a [], int left, int right) is to divide a [left] ~ a [right] according to an element X (such as a [left]) in a [left] ~ a [right]. After the division, the left segment of X is less than or equal to x, and the right segment is greater than or equal to X. at the same time, the position of X can be used to calculate the number of X in ascending non descending order of this batch of data. Therefore, we can program int find (int a [], int left, int right, int k) function, obtain the partition point by calling the partition function, and judge whether the partition point is the kth smallest. If not, recursively call find function to continue to search in the left or right segment.
###Input format:
There are two lines of input:
The first line is n and K, 0 < K < = n < = 10000
The second line is n integers
###Output format:
Output the kth smallest number
###Input example:
Here is a set of inputs. For example:
```in
10 4
2 8 9 0 1 3 6 7 8 2
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
answer：If there is no answer, please comment