快速找出第k小的数

问题很简单，就是从一堆数里找出第k小的数。

第一眼看到这个问题时，很可能会想到直接把这堆数进行升序排序，然后取第k个数就行了，这样的话时间复杂度为$O(nlogn)$ (使用高效的排序算法，比如快速排序)

当然，这种做法是可以接受的，至少从时间复杂度来说还不错，而且如果想取第k+1,k+2…小的数的时候也会变得很方便，但是如果我只想取第k小的数，在无形之中总感觉排序做的事情有点过多了！所以，还能再快一点吗？

考虑一个耳熟能详的问题，就是有若干个物品，其中有一个次品的质量较轻，怎么做才能最快的找到那个次品？对于这个问题，都知道是利用二分法来解决是最快的，即将这堆物品平均分成两份并比较这两堆的重量，得到质量较轻的那一堆后，再平均分成两堆进行同样的操作......最后便可以找到那个次品！

同样的道理，对于从一堆数中找出第k小的数，我们可以假定一个分界线，比如把比$ n $小的数放在一堆，把比$ n $大的数放在一堆，假设这两堆分别有$a$,$ b $个数，当$ a $比$ k $小时，显然可以得出我们要找的第$ k $小的数在后面那一堆；当$ a $比$ k $大时，第$ k $小的数在便就在前面这一堆里边。

那么，具体怎么操作呢？我们回顾一下快速排序算法，是不是能发现快速排序算法中每一次操作的结果就是把比基数小的数放在基数前面，比基数大的数放在后面？这正好就是我们想要进行的操作！所以，可以考虑将快速排序进行变形，便可以像二分法那样快速地找到第$ k $个数了。

#include<bits/stdc++.h>
using namespace std;

int find_K_min(vector<int>v,int left,int right,int k);

int main(){
    vector<int>v;
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;++i){
        int a;
        cin>>a;
        v.push_back(a);
    }

    cout<<find_K_min(v,0,v.size()-1,k);

}

int find_K_min(vector<int>v,int left,int right,int k){
    int base=v[left];
    int i=left,j=right;
    while(i<j){
        while(v[j]>base&&i<j) j--;
        while(v[i]<=base&&i<j) i++;
        int tmp=v[i];
        v[i]=v[j];
        v[j]=tmp;
    }

    int tmp=v[i];
    v[i]=v[left];
    v[left]=tmp;


    if(i==k-1) return v[i];
    if(i>k-1)  return find_K_min(v,left,i-1,k);
    else return find_K_min(v,i+1,right,k);
}