【acwing】786. 第k个数

穿越隧道

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n,k;
int qs(int l, int r, int k){
    
    if(l == r) return q[l];
    int i = l - 1, j = r + 1, x = q[(l + r)/2];
    while(i < j){
    
        while(q[++i] < x) ;//实现左区间向右边前进，右区间向左边前进
        while(q[--j] > x) ;
        if(i < j) swap(q[i],q[j]);
    }
    int s1 = j - l  + 1;//找到当时分界点在区间的位置，因区间从0开始，所以要加1
    if(k <= s1)//当所要查询的数，在当前分界点的左边时，则进行左递归，否则进行右递归。
        return qs(l, j, k);
    return qs(j + 1,r, k - s1);
    
}
int main(){
    
    scanf("%d%d",&n,&k);
    for(int i = 0; i < N; i++){
    
        scanf("%d",&q[i]);
    }
    cout << qs(0,n-1,k) << endl;
    return 0;
}