引言：用Js攻略leetcode中的算法，将会介绍自己的思路和注意点，一边学习一边愉快刷题呀。
问题：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
你可以假设 nums1 和 nums2 不同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
思考:
总体思考：
最主要的难点是算法复杂度的限制， log级别的时间复杂度我们自然想到二分法，每次取中间值，自然得出的是log2(n)级别的。
因为nums1和nums2是有序数组，我们对这两个数组分别在某一位置进行划分。
比如nums1数组设为A， 划分位置为 i ：
left_A | right_A
A [0]，A [1]，...，A [i-1] | A [i]，A [i + 1]，...，A [m-1]
这样左边有 i 个元素，右边有（ m - i ）个元素。
nums2数组设为B，划分位置为 j :
left_B | right_B
B [0]，B [1]，...，B [j-1] | B [j]，B [j + 1]，...，B [n-1]
这样左边有 j 个元素，右边有（ n - j ）个元素。
把两个数组的左右两边分别混合，也就是left_A和left_B放一起，right_A和right_B放一起，得到中位数需要满足下面两个条件：
- 左右数量相等（偶数：i + j = m - i + n -j ）或者左边比右边大一个（奇数：i + j = m - i + n -j + 1）
- max(left_A) 小于 min(right_B)，而且max(left_B) 小于 min(right_A)，因为left_A肯定小于right_A, left_B肯定小于right_B
那么对于总长度为奇数，中位数 = max(left_A, left_B)；对于总长度为偶数，中位数 = ( max(left_A, left_B) ，min(right_A，right_B) ) / 2
把上面两个条件进行整理：
-
i = 0〜m，j = parseInt( (m + n + 1) / 2) - i (奇偶通用，阴影划分的为左边，其他为右边)
总长度为奇数
总长度为偶数
所以n要大于等于m（n>=m），这样确保 j 是合法索引。
- shortArray[ i -1] <= longArray[ j ]，longArray[ j - 1 ] <= shortArray [ i ]
实现细节：
- 先对nums1和nums2的长度进行判断，选择长的作为longArray， 短的作为shortArray
- i 在 [ 0, m ]中进行取值，并根据二分法取中值，j = parseInt( (m + n + 1) / 2) - i
- 如果（ j > 0 && i < m && longArray[j-1] > shortArray[i] ），说明shortArray [i]太小，i 应该继续增大，取值范围变为 [ i + 1, m ]
- 如果（ i > 0 && j < n && shortArray[i-1] > longArray[j] ），说明shortArray [i]太大， i 应该减小，取值范围变为[0, i - 1]
- 以此循环，直到上面条件都不满足，说明要么取到边界了（i =0 , j=0 等情况），要么shortArray和longArray左边都取了值，要选出shortArray和longArray左边最大的值。
-
(i =0 情况下，左侧确定，左边最大值为longArray[j - 1] )
image.png -
(j = 0情况下，左侧确定，左侧最大值为shortArray[i - 1])
image.png -
(其他情况，shortArray和longArray左边都取了值)
image.png
- 对于总长度为奇数， 中位数 = max(left_A, left_B)， 也就是第5步得到的值。如果是奇数，要再得到 minRight.
代码：
var findMedianSortedArrays = function(nums1, nums2) {
var shortArray = [],longArray = [], m = nums1.length, n = nums2.length,
temp = 0, maxLeft = 0, minRight = 0;
//保证 n >= m
if(m > n) {
shortArray = nums2;
longArray = nums1;
temp = m;
m = n;
n = temp;
} else {
shortArray = nums1;
longArray = nums2;
}
//假设shortArray取i个，longArray取parseInt((m+n+1)/2)-i个
var imin = 0, imax = m, i, j;
do {
i = parseInt((imin + imax)/2);
j = parseInt((m + n + 1)/2 - i);
if(j > 0 && i < m && longArray[j-1] > shortArray[i]) {
// shortArray和longArray左右都取了值，且i值取小了
imin = i + 1;
} else if( i > 0 && j < n && shortArray[i-1] > longArray[j]) {
// shortArray和longArray左右都取了值，且i值取大了
imax = i - 1;
} else {
// 考虑边界情况
if(i == 0) {
maxLeft = longArray[j - 1];
} else if (j == 0 ) {
maxLeft = shortArray[i - 1];
} else {
// i值不小不大, 也就是(shortArray[i-1] <= longArray[j] && longArray[j-1] <= shortArray[i])
maxLeft = Math.max(shortArray[i - 1], longArray[j -1]);
}
break;
}
} while (imin <= imax);
//两数组相加个数是奇数，只要取中间值
if( (m + n)%2 == 1 ) return maxLeft;
//个数是偶数，必须左右两边中位数相加除以二
if(i == m) {
minRight = longArray[j];
} else if(j == n){
minRight = shortArray[i];
} else {
minRight = Math.min(shortArray[i], longArray[j]);
};
return (maxLeft + minRight)/2;
}
