(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);
- }
- }
- }
①～⑤处应填（ ）
1.
A. (m1 + m2) * 2
B. (m1 - 1) + (m2 - 1)
C. m1 + m2
D. (m1 + 1) + (m2 + 1)
2.
A. a1[m1] == a2[m2]
B. a1[m1] <= a2[m2]
C. a1[m1] >= a2[m2]
D. a1[m1] != a2[m2]
3.
A. left1 == right1
B. left1 < right1
C. left1 > right1
D. left1 != right1
4.
A. y = a1[k - left2 - 1]
B. y = a1[k - left2]
C. y = a2[k - left1 - 1]
D. y = a2[k - left1]
5.
A. y = a1[k - left2 - 1]
B. y = a1[k - left2]
C. y = a2[k - left1 - 1]
D. y = a2[k - left1]
