时间复杂度 $O(n)$ : $ \frac{n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \cdots + \frac{n}{2^n} \leq O(2n) $

主要是把当成某种下标来处理会更好，k在哪边就递归哪边，可以保证k始终在递归的区间内部，到区间只剩下一个值的时候，就找到了那个值

#include <iostream>
using namespace std;
constexpr int N = 1e5; 
int q[N+50], n, k;
int q_select(int l, int r, int k) {
  if(l == r) return q[l];//只剩下一个值的时候就结束递归
  int x = q[l + r >> 1], i = l - 1, j = r + 1;
  while(i < j) {
    do ++i; while(q[i] < x);
    do --j; while(q[j] > x);
    if(i < j) {
      swap(q[i], q[j]);
    }
  }
  int sl = j - l + 1;//这里求的是左区间的长度
  if(k <= sl) {
    return q_select(l, j, k);//k在区间内，就取左区间找
  } else {
    return q_select(j + 1, r, k - sl);//不在左边就去递归右边
  }
}

int main() {
  ios::sync_with_stdio(false),cin.tie(nullptr);
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    cin >> q[i];
  }
  cout << q_select(1, n, k) << "\n";
  return 0;
}