#1080. 求第 k 小的数

求第 k 小的数

题目描述

输入 nn1n<50000001 \le n < 5000000 )个数字 aia_i1ai<1091 \le a_i < {10}^9),输出这些数字的第 kk 小的数。最小的数是第 00 小。

请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。

输入格式

输入共2行

第01行:两个整数n和k,用空格隔开

第02行:n个整数

输出格式

输出共一行,一个整数表示n个数中第k小的数字

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2