题目是：求两个排序数组的中位数。
设：两个排序的数组a[m], b[n]，求a和b数组的中位数。
算法是：
mid_a是数组a的中位数index，同理mid_b是数组b的中位数索引
1. 如果a[mid_a] == b[mid_b] 中位数为a[mid_a]
2. 如果a[mid_a] < b[mid_b], 递归查找a(mid_a + 1, m - 1), b(0, mid_b)，因为a[mid_a]比较小，不可能作为下一次查询的中位数
3. 如果a[mid_a] > b[mid_b], 递归查找a(0, mid_a), b(mid_b + 1, n - 1)，因为b[mid_b]比较小，不可能作为下一次查询的中位数
4. 当只少于4个元素需要查找时递归停止，merge这少于4的元素，求出中位数。这里需要考虑奇偶数的情况，只剩下2个或3个元素，不如只考虑4个简单。
注意：这里求上中位数，当n为奇数时，中位数是唯一的，出现位置为n/2；当n为偶数时候，存在两个中位数，数组index从0开始，位置分别为n/2 - 1（上中位数）和n/2（下中位数）。
[cpp]
#include <iostream>
using namespace std;
class Solution {
public:
int find_median(int a[], int p, int q, int b[], int r, int s) {
int size_a = q - p + 1;
int size_b = s - r + 1;
int total_size = size_a + size_b;
if (total_size <= 4) {
// calcuate median for less than 4 elements
int i = p;
int j = r;
int num = (total_size + 1) / 2;
for (int k = 1; k < num; k++) {
// A fake merge without copying, just move index
if (i <= q && j <= s) {
if (a[i] <= b[j]) {
++i;
} else {
++j;
}
} else if (i > q) {
++j;
} else if (j > s) {
++i;
}
}
int median = 0;
if (i <= q && j <= s) {
median = a[i] < b[j] ? a[i] : b[j];
} else if (i > q){
median = b[j];
} else if (j > s) {
median = a[i];
}
return median;
}
int mid_a = get_median_index(a, p, q);
int mid_b = get_median_index(b, r, s);
if (a[mid_a] == b[mid_b]) {
return a[mid_a];
} else if (a[mid_a] < b[mid_b]) {
// mid_a is less, no need to be seached later, no possible to be median
return find_median(a, mid_a + 1, q, b, r, mid_b);
} else {
// mid_b is less, no need to be seached later, no possible to be median
return find_median(a, p, mid_a, b, mid_b + 1, s);
}
}
private:
int get_median_index(int a[], int p, int q) {
int n = q - p + 1;
int mid = n / 2;
if (n % 2 == 0) {
return p + mid - 1;
} else {
return p + mid;
}
}
};
int main(int argc, char const *argv[])
{
int a[] = {5, 6, 7, 8};
int m = sizeof(a) / sizeof(int);
int b[] = {1, 2, 3, 4};
int n = sizeof(b) / sizeof(int);
Solution s;
int median = s.find_median(a, 0, m - 1, b, 0, n - 1);
cout << median << endl;
return 0;
}
[/cpp]