CSP-S 提高级 · CSP 2022 提高级第一轮 第 19 题

三 完善程序（单选题，每小题 3 分，共计 30 分）

(1)（归并第 k 小） 已知两个长度均为 n 的有序数组 a1 和 a2（均为递增序，但不保证严 格单调递增），并且给定正整数 k（1≤k≤2n），求数组 a1 和 a2 归并排序后的数组里 第 k 小的数值。

试补全程序。

#include <bits/stdc++.h>
using namespace std;

int solve(int *a1, int *a2, int n, int k) {
    int left1 = 0, right1 = n - 1;
    int left2 = 0, right2 = n - 1;
    while (left1 <= right1 && left2 <= right2) {
        int m1 = (left1 + right1) >> 1;
        int m2 = (left2 + right2) >> 1;
        int cnt = ①;
        if (②) {
            if (cnt < k) left1 = m1 + 1;
            else right2 = m2 - 1;
        } else {
            if (cnt < k) left2 = m2 + 1;
            else right1 = m1 - 1;
        }
    }
    if (③) {
        if (left1 == 0) {
            return a2[k - 1];
        } else {
            int x = a1[left1 - 1], ④;
            return std::max(x, y);
        } 
    } else {
            if (left2 == 0) {
                retur

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是二分归并找第k小：每次取两数组当前区间中点，用中点下标之和作为已排除元素数cnt，比较中点值决定舍弃哪半边；循环直到某数组区间为空，再从另一数组按剩余k值取元素并与耗尽数组最后一个未排除元素比较。

①处最容易错选(m1+m2)*2或包含中点的下标，记住cnt是左半不含中点的元素总数，所以直接m1+m2；②处若写成>=会漏掉相等时该舍弃a1左半的情况，必须<=；③处判断条件是left1>right1表示a1区间已空，不是等于或小于；④⑤处下标要仔细：left1是已排除个数，从a2取就是a2[k-left1-1]，别把left1和left2搞混，也别漏掉-1导致越界。

这道题考查的是二分查找与分治算法的结合，具体场景是在两个有序数组中找归并后的第k小元素。命题人喜欢把这种经典算法包装成“完善程序”，考察学生对算法逻辑的拆解能力，特别是中点选取、排除区间判断以及边界处理。拿到题先想：两个有序数组合并，第k小一定在某个区间里，每次通过比较两个中点值，可以安全地排除掉一部分不可能的元素，这就是典型的二分思想。思考心法：先确定cnt代表什么——它应该是a1左半（不含中点）和a2左半（不含中点）的元素总数，这样cnt就表示“如果只看这两半，一共排掉了多少个元素”。因为数组下标从0开始，a1[0..m1-1]正好有m1个元素，a2同理，所以cnt=m1+m2，对应选项C。接下来判断怎么排除：若a1[m1]<=a2[m2]，说明a1左半整体都不大于a2中点，那么a1左半和a2右半都可以考虑排除；但题目逻辑是：如果cnt<k，说明第k小还在更后面，所以排除a1左半（left1=m1+1）；否则说明第k小在更前面，排除a2右半（right2=m2-1）。这里的关键是<=，选B。循环结束时，必然有一个数组的区间先空了。代码里用if(left1>right1)判断a1是否先空，对应选项C。a1先空时，如果left1==0，说明a1一个都没用，直接返回a2[k-1]；否则a1最后一个未被排除的元素是a1[left1-1]，而我们需要的是a2中第(k-left1)个元素（0-based），即a2[k-left1-1]，对应选项C。对称地，a2先空时，返回a1[k-left2-1]，对应选项A。易错点在于①处容易误选(m1+m2)*2或包含中点的下标，记住cnt是左半不含中点的元素总数；②处若写成>=会漏掉相等时该舍弃a1左半的情况；③处判断条件是left1>right1表示a1区间已空，不是等于或小于；④⑤处下标要仔细：left1是已排除个数，从a2取就是a2[k-left1-1]，别把left1和left2搞混，也别漏掉-1导致越界。从考频看，二分查找在题库中累计39题，覆盖7个级别，近年趋势明显上升：2024年9题、2025年7题、2026年5题，说明命题人持续偏爱二分；分治算法累计79题，2024年17题、2025年14题、2026年15题，同样处于高位。基于这些数据，未来这类“双数组第k小”的二分归并题目大概率还会在CSP提高级、NOIP模拟卷中出现，难度可能略有提升（比如数组长度不等或k接近2n），但核心思路不变。暂无足够依据预测具体年份和分值，但把握二分与分治的结合点是稳妥的。