最简单的方法是两个数组一个一个往前找找到中间那个数结束。但是时间复杂度是O(m+n)。既然要求复杂度为O(log(m+n))，所以几乎一定是二分查找。而且应该也不用一个挨着一个找。
许多corner case干扰推导：
- m + n是奇数还是偶数？奇数的话要取第(m+n)/2 + 1个数。偶数的话要取第(m+n)/2个和第(m+n)/2 + 1个数的平均数？解决方法是设置helper函数，题目本质为：取两个数组的第k大的数。所以判断先判断奇偶，偶的话返回两个helper结果的平均数。
- m和n谁大？应该一直假设m比n大，如果不是的话，helper两个数组反过来。
- 开始二分法，两边都取第k/2个数（实际编码时候index=[k/2] -1）
a. 如果m(k/2) < n(k/2)， 那m这边0~k/2都在前k个里面，换言之，中位数（第k个大的数）肯定不在这里面。（为什么？反证法，如果中文数在m的前k/2里面，那m这边最多k/2 - 1个数，n那边第k/2个比m这边第k/2个大，所以肯定也不是中位数，所以也是最多k/2 - 1个数，最后加一块儿k-2个数，少于k个数。
所以要把m这边的前k/2个都算进去，然后继续找m后一半和n的全部，找第k - k/2 = k/2个数
b. 如果m(k/2) = n(k/2)，那如果k为奇数，就是这个数后面那个m和n里面比较小的数。如果k为偶数，就是这俩数。 - 特殊情况
a. 最后越来越少不够k/2： 所以要取pa = min(k/2, m),另一边 pb = k - pa而不是简单的两边都是k/2
b. k = 1时上面算法不需要，也是停止点， 否则pa = 0, pb = 1, 数组index = pa -1是非法值。
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
if((m + n) % 2 == 1){
return (double)FindKthLargest(nums1, m, nums2, n, (m + n) / 2 + 1);
}
return (FindKthLargest(nums1, m, nums2, n, (m + n) / 2) + FindKthLargest(nums1, m, nums2, n, (m + n) / 2 + 1)) / 2;
}
public double FindKthLargest(int[] a, int m, int[] b, int n, int k){
if(m > n){
return FindKthLargest(b, n, a, m, k);
}
if(m == 0){
return b[k - 1];
}
if(k == 1){
return Math.Min(a[0], b[0]);
}
//Divide k into two parts
int pa = Math.Min(m, k / 2);
int pb = k - pa;
if(a[pa - 1] < b[pb - 1]){
int[] subArray = new int[m - pa];
Array.Copy(a, pa, subArray, 0, m- pa);
return FindKthLargest(subArray, m - pa, b, n, k - pa);
}
else if (a[pa - 1] > b[pb - 1]){
int[] subArray = new int[n - pb];
Array.Copy(b, pb, subArray, 0, n - pb);
return FindKthLargest(a, m , subArray, n - pb, k - pb);
}
return a[pa - 1];
}
}
