題目：
有兩個大小為 n 和 m 的排序數(shù)組nums1?和nums2?。
請找出兩個排序數(shù)組的中位數(shù)并且總的運行時間復雜度為?O(log (m+n)) 。
There are two sorted arrays?nums1?and?nums2?of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
思路：
最簡單直接的辦法就是合并數(shù)組，再取中位數(shù)。但是時間復雜度為O(m+n) >?O(log (m+n))，不符合要求。
略加思索，中位數(shù)與位置相關(guān)。在一個總長m + n的數(shù)組里分割數(shù)組的index為(m+n-1)/2。
兩個數(shù)組內(nèi)小于等于中位數(shù)的數(shù)的個數(shù)必定等于兩個數(shù)組內(nèi)大于等于中位數(shù)的數(shù)的個數(shù)。根據(jù)這一特性，我們只要在兩個數(shù)組里找到兩個index，使得?[0, index1) + [0, index2）= （index1, n] + (index2, m]，便可根據(jù)index算出中位數(shù)。
由以上推論不難得出：
index1 + index2 = (m + n - 1) / 2 - 1 / 2
index1?∈ [ -1 / 2, n - 1 / 2 ]
index2?∈ [ -1 / 2, m - 1 / 2 ]
所有滿足以上條件的index1和index2，都能使得兩個分割的數(shù)組左邊和右邊數(shù)的個數(shù)和相等。但并不能保證index1， index2附近就能取到中位數(shù)。
若index1，index2 為整數(shù)，則nums1[index1], nums2[index2]所取之數(shù)就是兩個數(shù)組的“分割數(shù)”，如果兩個分割數(shù)相同，則該分割數(shù)一定為中位數(shù)。
若index1，index2 不為整數(shù)，則與index鄰近的兩個整數(shù)能取出兩個數(shù)，即：
l1 = nums1[Math.floor(index1)]
r1 = nums1[Math.ceil(index1)]
l2 = nums2[Math.floor(index2)]
r2 = nums2[Math.ceil(index2)]
那如何根據(jù)這4個數(shù)判斷出中位數(shù)呢？看到這里有人可能已經(jīng)明白了。沒明白也沒關(guān)系，我們來舉個栗子。
如: [1, 2, 3], [3, 4, 5]兩數(shù)組，總長為6，中位數(shù)分割的index為2.5。
設(shè)定nums1的長度n大于等于nums2的長度m。
若nums2的最小值大于nums1的最大值，那么中位數(shù)分割index在(m+n-1)/2處。
若nums1的最小值大于nums2的最大值，那么中位數(shù)分割index在(n-m-1)/2處。
index1 + index2 = 2
index1?∈ [ -0.5, 2.5 ]
index2?∈ [ -0.5, 2.5 ]
我們讓index1在[ -0.5, 2.5 ]以0.5為步長遍歷，初次結(jié)果：
index1: -0.5,
index2: 2.5,
l1: -∞,
r1: 1,
l2: 5,
r2: +∞;
最后一次結(jié)果（正確結(jié)果）：?
index1: 2.5,
index2: -0.5,
l1: 3,
r1: +∞,
l2: -∞,
r2: 3;
對比兩次結(jié)果，不難發(fā)現(xiàn)以合法結(jié)果中[l1, r1] [l2, r2]是有交集的，即[max(l1,l2), min(r1, r2)]是有效的。
同時如果n+m為奇數(shù)，中位數(shù)max(l1,l2) = min(r1, r2)；
如果n+m為偶數(shù)，中位數(shù)為(max(l1,l2) + min(r1, r2))/2。
此時算法的循環(huán)次數(shù)為((m+n-1)/2 - (m-n-1)/2)*2 = 2m, 時間復雜度為O(2m)，離題目的復雜度還有差距。
我們再把逐步循環(huán)替換成二分查找，就可以把復雜度降為O(log(2m)) < O(log(n+m))。
代碼：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
function setWithDefaultValue(value, defaultValue) {
? ? return value === undefined ? defaultValue : value;
}
var findMedianSortedArrays = function(nums1, nums2) {
? ? if(nums1.length < nums2.length) {
? ? ? ? return findMedianSortedArrays(nums2, nums1);
? ? }
? ? n = nums1.length;
? ? m = nums2.length;
? ? let l1, l2, r1, r2;
? ? const totalIndex = (n + m - 1)/2;
? ? let startIndex = (n - m - 1)/2, endIndex = totalIndex;
? ? while(true) {
? ? ? ? const i = Math.floor(startIndex + endIndex) / 2;
? ? ? ? const j = totalIndex - i - 0.5;
? ? ? ? l1 = setWithDefaultValue(nums1[Math.floor(i)], -Infinity);
? ? ? ? r1 = setWithDefaultValue(nums1[Math.ceil(i)], Infinity);
? ? ? ? l2 = setWithDefaultValue(nums2[Math.floor(j)], -Infinity);
? ? ? ? r2 = setWithDefaultValue(nums2[Math.ceil(j)], Infinity);
? ? ? ? if(l1 > r2) {
? ? ? ? ? ? endIndex = i - 0.5;
? ? ? ? } else if(l2 > r1) {
? ? ? ? ? ? startIndex = i + 0.5;
? ? ? ? } else {
? ? ? ? ? ? return (Math.max(l1, l2) + Math.min(r1, r2))/2;
? ? ? ? }
? ? }
? ? return 0;
};
