【acwing】786. Number k

Through the tunnel

#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) ;// Realize the left section to move forward to the right , The right section advances to the left 
        while(q[--j] > x) ;
        if(i < j) swap(q[i],q[j]);
    }
    int s1 = j - l  + 1;// Find the position of the dividing point in the interval at that time , Due to interval from 0 Start , So add 1
    if(k <= s1)// When the number to be queried , When it is on the left of the current dividing point , Then left recursion , Otherwise, right recursion .
        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;
}