原题目为Median of Two Sorted Arrays，这里被我改成了更为通用的名字和函数。
这是一道非常经典的题。这题更通用的形式是，给定两个已经排序好的数组，找到两者所有元
素中第 k 大的元素。
O(m + n) 的解法比较直观，直接 merge 两个数组，然后求第 k 大的元素。
不过我们仅仅需要第 k 大的元素，是不需要“排序”这么复杂的操作的。可以用一个计数器，
记录当前已经找到第 m 大的元素了。同时我们使用两个指针 pA 和 pB，分别指向 A 和 B 数组的第
一个元素，使用类似于 merge sort 的原理，如果数组 A 当前元素小，那么 pA++，同时 m++；如果
数组 B 当前元素小，那么 pB++，同时 m++。最终当 m 等于 k 的时候，就得到了我们的答案，O(k)
时间，O(1) 空间。但是，当 k 很接近 m + n 的时候，这个方法还是 O(m + n) 的。
有没有更好的方案呢？我们可以考虑从 k 入手。如果我们每次都能够删除一个一定在第 k 大元
素之前的元素，那么我们需要进行 k 次。但是如果每次我们都删除一半呢？由于 A 和 B 都是有序
的，我们应该充分利用这里面的信息，类似于二分查找，也是充分利用了“有序” 。
假设 A 和 B 的元素个数都大于 k/2，我们将 A 的第 k/2 个元素（即 A[k/2-1]）和 B 的第 k/2
个元素（即 B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设 k 为偶数，所得到的结
论对于 k 是奇数也是成立的） ：
• A[k/2-1] == B[k/2-1]
• A[k/2-1] > B[k/2-1]
• A[k/2-1] < B[k/2-1]
如果 A[k/2-1] < B[k/2-1]，意味着 A[0] 到 A[k/2-1 的肯定在 A ∪ B 的 top k 元素的范围
内，换句话说，A[k/2-1]不可能大于 A ∪ B 的第 k 大元素。留给读者证明。
因此，我们可以放心的删除 A 数组的这 k/2 个元素。同理，当 A[k/2-1] > B[k/2-1] 时，可
以删除 B 数组的 k/2 个元素。
当 A[k/2-1] == B[k/2-1] 时，说明找到了第 k 大的元素，直接返回 A[k/2-1] 或 B[k/2-1]
即可。
因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？
• 当 A 或 B 是空时，直接返回 B[k-1] 或 A[k-1]；
• 当 k=1 是，返回 min(A[0], B[0])；
• 当 A[k/2-1] == B[k/2-1] 时，返回 A[k/2-1] 或 B[k/2-1]
上述分析引用了LeetCode 题解，需要一点说明：
（1）
<pre name="code" class="cpp"> A[k/2-1] < B[k/2-1]，意味着 A[0] 到 A[k/2-1] 的肯定在 A ∪ B 的 top k 元素的范围
内，换句话说，A[k/2-1]不可能大于 A ∪ B 的第 k 大元素。留给读者证明。
证明：这里使用反证法，假设A[K/2-1]大于第k大的元素，那么A[K/2-1]以后的元素就不该在
topk里面了，因此B中下标在K/2-1以后一定至少有一个在topk，但是显然该元素大于A[K/2-1]
与前提矛盾，即证。（写的有点糙，凑活看，还需要考虑奇数偶数等）
（2）
变成中实际两个数组的长度不一定比K/2大，因此还要合理划分范围。
#include <iostream>
using namespace std;
class solution
{
public:
/*在两个升序排序的数组中找到第k大的元素*/
int FindKthInTwoSortedArray(int array1[], int len1, int array2[],int len2, int k)
{
if( k < 0 )
{
cout<<"Invalid k = "<<k<<endl;
return -1;
}
/*保证 len1 <= len2*/
if( len1 > len2 )
return FindKthInTwoSortedArray(array2,len2, array1,len1, k);
if( len1 == 0 )
return array2[k-1];
if( k == 1)
return ((array1[0]>= array2[0]) ? array2[0] : array1[0]);
/*不一定每个数组都有k/2个元素*/
int num1 = (len1 >= k/2) ? k/2 : len1;
int num2 = k - num1;
if( array1[num1-1] == array2[num2-1] )
return array1[num1-1];
else if( array1[num1-1] > array2[num2-1] )
{
return FindKthInTwoSortedArray(array1, len1, &array2[num2], len2-num2, k-num2);
}
else if( array1[num1-1] < array2[num2-1] )
{
return FindKthInTwoSortedArray(&array1[num1], len1-num1, array2, len2, k-num1);
}
}
};
int main()
{
solution s;
int ret;
int i;
int array1[11] = {0,1,2,3,4,5,6,7,8,9,17};
int array2[11] = {3,4,5,6,7,8,9,10,11,12,29};
cout<<"sorted two array:"<<endl;
for(i=1; i<=22; i++)
{
ret = s.FindKthInTwoSortedArray(array1, 11, array2, 11, i);
cout<<i<<"th: "<<ret<<endl;
}
}