三 完善程序（单选题，每小题 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) {return a1[k - 1];} else {int x = a2[left2 - 1], ⑤;return std:: max(x, y);}} }
二、分析程序
本体已经指明代码的意思：在两个序列中找出第k小的值，所以我们直接看代码。
该程序没有main()函数，我们直接看到solve()函数。
其中，该算法使用了二分的方法。
while 循环中，在没有出现无效区间的情况下，执行了一下几个任务。
我们举一个例子带入进去：
n = 5, k = 4
a = [1, 2, 4, 5, 7]
b = [3, 6, 8, 9, 11]
第一次循环：
left1 = 0，right1 = 4，m1 = 2
left2 = 0，right2 = 4，m2 = 2
cnt 应该是m1 + m2 = 4，因为此时m1，2前面的个数达到了4，够了。
接下来，我们应该对a[m1]，b[m2]进行比较，取走小者，大者留在后面放进去
a[2] < b[2]：
cnt >= k，所以缩小大者的右边，right2 = m2 - 1 = 1。
第二次循环：
left1 = 0，right1 = 4，m1 = 2
left2 = 0，right2 = 1，m2 = 0
cnt = 2 + 0 = 2
a[2] > b[0]，所以进入到第二个分支：
cnt < k，所以增加小者的右边，left2 = m2 + 1 = 1
第三次循环：
left1 = 0，right1 = 4，m1 = 2
left2 = 1，right2 = 1，m2 = 1
cnt = 3
a[2] < b[1]：
cnt < k，所以增加小者的右边，left1 = m1 + 2 = 3
第四次循环：
left1 = 3，right1 = 4，m1 = 3
left2 = 1，right2 = 1，m2 = 1
cnt = 4
a[3] < a[1]，所以缩小大者的右边，right1 = m1 - 1 = 2
循环结束。
循环结束后我们要按分情况返回。
第一种情况：left1 > right1 结束：
这里判断一下是不是left1 == 0，如果是的话返回a2中前k个的的最大值也就是a2[k - 1]，因为这样子一定是right1靠过来才结束的。
如果不是，则说明两端都有操作，我们返回a1，a2中前若干个的最大值。
第二种情况：left2 > right2 结束：
判断是不是left2 == 0，如果是则同理，返回a1[k - 1]。
否则同理。
三、题目分析
①～⑤处应填：
- A. (m1 + m2) * 2
B. (m1 - 1) + (m2 - 1)
C. m1 + m2
D. (m1 + 1) + (m2 + 1)【正确答案： C，因为cnt记录m1, 2之前有几个数】
- A. a1[m1] == a2[m2]
B. a1[m1] <= a2[m2]
C. a1[m1] >= a2[m2]
D. a1[m1] != a2[m2]【正确答案： B，因为此次判断两数大小，取小者选入】
- A. left1 == right1
B. left1 < right1
C. left1 > right1
D. left1 != right1【正确答案： C，判断是那种情况跳出循环，若是因为序列1则执行下面语句】
- A. y = a1[k - left2 - 1]
B. y = a1[k - left2]
C. y = a2[k - left1 - 1]
D. y = a2[k - left1]【正确答案： C，用k减去left1则是另一个序列中的选中的最后一个值，但是由于从0开始，所以下标还要 - 1】
- A. y = a1[k - left2 - 1]
B. y = a1[k - left2]
C. y = a2[k - left1 - 1]
D. y = a2[k - left1]【正确答案： A，与上题同理~】
