c++ 分治法求k1到k2

假设要在一个数组 `arr` 中求第 `k1` 到第 `k2` 小的数，可以使用分治法来解决。

具体思路如下：

1. 将数组 `arr` 分成两个部分，左边部分小于等于某个值 `mid`，右边部分大于 `mid`。
2. 计算左边部分的个数 `cnt`，如果 `cnt >= k2`，则说明第 `k1` 到第 `k2` 小的数在左边部分中，递归处理左半部分。
3. 如果 `cnt < k1`，则说明第 `k1` 到第 `k2` 小的数在右半部分中，递归处理右半部分。
4. 否则，说明第 `k1` 到第 `k2` 小的数就是左半部分中排名为 `(k1 - 1)` 的数，直接返回即可。

具体实现如下：

int kth_element(vector<int>& arr, int k) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int pivot = arr[right];
        int i = left;

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                swap(arr[i], arr[j]);
                i++;
            }
        }

        swap(arr[i], arr[right]);

        if (i == k - 1) {
            return arr[i];
        } else if (i > k - 1) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }

    return -1;
}

int kth_smallest(vector<int>& arr, int k1, int k2) {
    int n = arr.size();
    int k1_val = kth_element(arr, k1);
    int k2_val = kth_element(arr, k2);

    vector<int> left_arr;
    vector<int> middle_arr;
    vector<int> right_arr;

    for (int i = 0; i < n; i++) {
        if (arr[i] < k1_val) {
            left_arr.push_back(arr[i]);
        } else if (arr[i] >= k1_val && arr[i] <= k2_val) {
            middle_arr.push_back(arr[i]);
        } else {
            right_arr.push_back(arr[i]);
        }
    }

    int cnt = middle_arr.size();

    if (cnt >= (k2 - k1 + 1)) {
        return kth_element(middle_arr, k2 - k1 + 1);
    } else if (cnt < (k1 - 1)) {
        return kth_smallest(right_arr, k1 - cnt - 1, k2 - cnt - 1);
    } else {
        return k1_val;
    }
}

其中，`kth_element` 函数用于求第 `k` 小的数，`kth_smallest` 函数用于求第 `k1` 到第 `k2` 小的数。时间复杂度为 $O(n \log n)$。