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)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
給出兩個有序數(shù)組，找出合并后的中位數(shù)，給了個限制條件時間在O(log(m + n)),看到log那就肯定是用二分法了峦耘。
先扯個遠一點的，中位數(shù)就是數(shù)組中間的那個數(shù)，求法和數(shù)組長度的奇偶有關(guān)平道，這里介紹個方法可以無視奇偶。核心的原理在于計算機除法的向下取整供炼，6/2=7/2=3一屋。
偶數(shù)時：[1,2,3,4,5,6]，midden=(3+4)/2=(arr[2]+arr[3])/2=(arr[n/2-1]+arr[n/2])/2.
n/2-1=(n-2)/2,由于向下取整劲蜻，4/2=5/2陆淀，所以(n-2)/2=(n-1)/2.
于是midden=(arr[(n-1)/2]+arr[n/2])/2；
奇數(shù)時:[1,2,3,4,5],midden=3=arr[2]先嬉，同樣由于向下取整轧苫，n=5，n/2=(n-1)/2.
midden=arr[n/2]=arr[(n-1)/2]=(arr[(n-1)/2]+arr[n/2])/2;
綜上：無論奇偶疫蔓，midden=(arr[(n-1)/2]+arr[n/2])/2含懊，記住核心原理，計算機除法的向下取整
回到題目中衅胀，我們假設(shè)A數(shù)組和B數(shù)組合二為一（當然不可能在程序中合并岔乔，時間限制不允許）
A+B=C,我們假設(shè)C是排好序的新數(shù)組，現(xiàn)在C可以分為L和R兩部分滚躯，L中的所有元素R中的
所有元素雏门。L可以分為A1和B1，同樣R可以分為A2和B2掸掏。因為A1<A2茁影，B1<B2必然成立，因為
A和B是有序數(shù)組丧凤，所以L<R成立還需要的條件是A1<=B2,B1<=A2募闲。
最后迭代C1和C2來比較，有三種可能
（1）A1>B2說明x需要減小愿待，A1存在過多元素
（2）A2<B1說明x需要增大浩螺，A1存在元素過少
（3）A1<=B2,B1<=A2，符合要求仍侥，此時midden=（max(A1要出，B1)+min(A2,B2)）/2
但似乎這只適用于偶數(shù)情況下，奇數(shù)情況下农渊，例如
[1,3,5,7,9]
[2,4,8,9]并不能得到正確結(jié)果厨幻，所以還需要我們作進一步處理
下面是這個題解的精髓
A: [1,2,3,4,5]--------->[#,1,#,2,#,3,#,4,#,5,#],長度變?yōu)?n+1
B: [1,1,1,1]------------>[#,1,#,1,#,1,#,1,#],長度變?yōu)?m+1
借助標記符號#，C總長度為2n+2m+2，這樣就變成了偶數(shù)個况脆，可以找到一處切割成長度相等的兩部分饭宾，長度都為m+n+1。在A中C1位置切割格了，相應(yīng)的就要在B的C2=m+n-x處切割看铆。
C1=7時，C2=4+5-7=2盛末，切割位置如下
[＃1＃2＃3＃（4/4）＃5＃]
[＃1/1＃1＃1＃]
A1=A2為3弹惦，B1=0菲驴，B2=1竞慢，找出如下關(guān)系
A1 = A [（C1-1）/ 2]; A2 = A [C1 / 2];
B1 = B[（C2-1）/ 2]; B2 = B [C2 / 2];
由于允許A1=A2或者B1=B2，人為的把奇偶變成了一種情況
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if (m < n) return findMedianSortedArrays(nums2, nums1);
if (n == 0) return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0;
int left = 0, right = 2 * n;
while (left <= right) {
int mid2 = (left + right) / 2;
int mid1 = m + n - mid2;
double L1 = mid1 == 0 ? Double.MIN_VALUE : nums1[(mid1 - 1) / 2];
double L2 = mid2 == 0 ? Double.MIN_VALUE : nums2[(mid2 - 1) / 2];
double R1 = mid1 == m * 2 ? Double.MAX_VALUE : nums1[mid1 / 2];
double R2 = mid2 == n * 2 ? Double.MAX_VALUE : nums2[mid2 / 2];
if (L1 > R2) left = mid2 + 1;
else if (L2 > R1) right = mid2 - 1;
else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
}
return -1;
}
}
