找无序数组中第k小的数

Question

问题遇到的现象和发生背景

想设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。

用代码块功能插入代码，请勿粘贴截图

#include<iostream>
using namespace std;
int partition(int a[],int p,int r)
{
    int i,j,t;
    i=-1,j=0;
    while(j<r)
    {
        if(a[j]<=a[r])   //need"=" 
        {
            t=a[i+<span class="hljs-number">1],a[i+1]=a[j],a[j]=t;
            i++,j++;
        //    cout<<"xxx" <<endl;
        }
        else
        {
            j++;
        //        cout<<"ooo" <<endl;
        }
    }
    
    
    t=a[r],a[r]=a[i+1],a[i+1]=t;
    //cout<<a[r]<<" "<<a[i+1];
    return i+1;
}


int find(int a[],int p,int r,int k)
{   if(p<r)
{

    int q=partition(a,p,r);
    if(q==k-1) {
    return a[q];}
    else if (q<k-1)  find(a,q+1,r,k);
    else if (q>k-1)  find(a,p,q-1,k);
}

}

int main()
{
    int a[2000];
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    cin>>a[i];
    
         cout<<find(a,0,n-1,k); //绛旀
         cout<<"   test point: "; 
        for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    
    
    
}

运行结果及报错内容

这个3到底是哪里来的啊？
我数组里都没有3

我的解答思路和尝试过的方法

就是一边划分一边比较其中心点地址与k来判断是否符合要求

我想要达到的结果

输入：6 4
1 1 4 5 1 4

输出：4

示例中的3到底是怎么出来的求解答

Answer 1

完全没看出来这个算法怎么能是O(n)的时间复杂度。用了类似二分的递归，怎么也不会是O(n)啊
而且逻辑也没看明白。
假设是 5 6 4 3 2 1 你这处理顺序是什麽呢？和最右边的值比较，为什麽呢？
find函数有两个漏洞，一是只考虑p<r，当p>=r时，没有返回值，导致函数没有返回值；二是递归函数应该为 return find(a,q+1,r,k);这样子，否则也是没有返回值。由于没有正确返回值，所以main你cout出来的3是个垃圾值而已。实际你的代码找不到第4小的数