题目描述：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例1:
nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
思路分析：
思路一：最简单的想法，用空间换时间，由于两个数组已经是有序的了。新建一个数组，其长度为m+n，利用两个指针分别遍历两个数组，将较小的放入新数组。最后的停止条件，其中一个数组遍历结束。再进行一次判断，将未遍历完的数组继续添加到新数组中。这样的时间复杂度为O(m+n)。
思路二：利用二分来解决，也是这道题实际要考察的内容。看了来自leetcode的官方题解，整个过程还是比较繁琐的。链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/
还有一个比较好理解的题解：
代码：
思路一：
1 class Solution { 2 public: 3 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 4 int len1 = nums1.size(); 5 int len2 = nums2.size(); 6 if(len1<=0 && len2<=0) 7 return 0; 8 vector<int> all; 9 int i,j; 10 for(i=0,j=0; i<len1&&j<len2;) 11 { 12 if(nums1[i]<=nums2[j]) 13 { 14 all.push_back(nums1[i]); 15 i++; 16 } 17 else 18 { 19 all.push_back(nums2[j]); 20 j++; 21 } 22 } 23 while(i<len1) 24 { 25 all.push_back(nums1[i]); 26 i++; 27 } 28 while(j<len2) 29 { 30 all.push_back(nums2[j]); 31 j++; 32 } 33 if((len1+len2)%2==1) 34 return all[all.size()/2]*1.0; 35 else 36 return (all[all.size()/2]+all[all.size()/2-1])/2.0; 37 } 38 };
思路二：
1 class Solution { 2 public: 3 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 4 int n = nums1.size(); 5 int m = nums2.size(); 6 7 if (n > m) //保证数组1一定最短 8 { 9 return findMedianSortedArrays(nums2, nums1); 10 } 11 12 // Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。 13 int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; //我们目前是虚拟加了'#'所以数组1是2*n长度 14 15 while (lo <= hi) //二分 16 { 17 c1 = (lo + hi) / 2; //c1是二分的结果 18 c2 = m + n - c1; 19 20 LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2]; 21 RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2]; 22 LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2]; 23 RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2]; 24 25 if (LMax1 > RMin2) 26 hi = c1 - 1; 27 else if (LMax2 > RMin1) 28 lo = c1 + 1; 29 else 30 break; 31 } 32 return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0; 33 } 34 35 };