include [HTML_REMOVED]
include [HTML_REMOVED]
//有一点二分的思想
//已知快排相当于把一个大区间分为两个小区间,左区间的数都小于一个数,右区间的都大于
//那么如果分界点也就是j,比k大,就证明右边所有数都比数组排序后第k个数大
//所以按从小到大排序,k一定在左区间
//同理如果j小于k,那么k就在右区间,然后递归,知道找到唯一k值,这也是前面所说与二分类似之处
//注意!!这里的k从进入sort函数里面后,便是当前所在区间的相对位置。
using namespace std;
const int N = 100010;
int a[N];
int quick_sort(int a[],int l,int r,int k)
{
if(l==r) return a[l];
int x=a[(l+r)>>1],i=l-1,j=r+1;
while(i[HTML_REMOVED]x);
if(i[HTML_REMOVED]=k) return quick_sort(a,l,j,k);//如果k在左区间,相对位置不变
else return quick_sort(a,i+1,r,k-(j-l+1));//在右区间,原来有区间的开始点,变为
//新区间的左区间。k实际相当于右移,右移单位是左区间长度,也就是j-l+1。
}
int main()
{
int n,k;
scanf(“%d%d”,&n,&k);
int i;
for(i=1;i<=n;i++) scanf(“%d”,&a[i]);
int p=quick_sort(a,1,n,k);
printf(“%d\n”,p);
return 0;
}