Median of Two Sorted Arrays

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)).

思路：

二分查找。对于两个有序数列，假设他们的长度分别为m和n，考虑最简单的情况，假设该中位数在长为m的数列中，且下标为i，则我们知道该数列中有i个(下标为0~ i-1)数小于它，又因为该数是两个数列的中位数，因此我们还能知道另一个数列中有多少数小于它。

解法：我们取长度小的那一个数列，进行二分查找，枚举分割的位置，设该分割为pm,则我们根据两数列大小的一半，可以计算出对应的另一个数列中的分割pn，

有pn = (m + n + 1) / 2 - pm。这样做，使得m数列中位于pm左侧的数以及n数列中位于pn左侧的数一共占总数的一半。如果所求的中位数就在这两个分割两侧的话，则有M[pm - 1] < N[pn] 且N[pn - 1] < M[pm]。否则的话，就按照二分查找的规则继续查找下一个分割pm。

找到后，假设两数组共有奇数个数字，则中位数为1个，且为M[pm - 1]和N[pn - 1]中较大的一个（或存在的一个）。若有偶数个数字，则应为奇数时的结果加上M[pm]和N[pn]中较少的那个数字(当pm = len(M)时，为N[pn]; pn = len(N)时，为M[pm]) 然后除以二。

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
 4         int len1 = nums1.size(), len2 = nums2.size();
 5         if (len1 > len2) return findMedianSortedArrays(nums2, nums1);
 6         if (len1 == 0) return (double)(nums2[(len2 - 1)/ 2] + nums2[len2 / 2]) / 2.0;
 7         int left = 0, right = len1, para = (len1 + len2 + 1) / 2;
 8         while (left <= right)
 9         {
10             int mid = (left + right) >> 1;
11             int tho = para - mid;
12             if (mid > 0 && tho < len2 && nums1[mid - 1] > nums2[tho])
13                 right = mid;
14             else if (tho > 0 && mid < len1 && nums2[tho - 1] > nums1[mid])
15                 left = mid + 1;
16             else
17             {
18                 int cand1 = INT_MIN, cand2 = INT_MIN;
19                 if (mid > 0) cand1 = nums1[mid - 1];
20                 if (tho > 0) cand2 = nums2[tho - 1];
21                 if ((len1 + len2) % 2)
22                     return (double)max(cand1, cand2);
23                 else
24                 {
25                     int rightMargin;
26                     if (mid == len1) rightMargin = nums2[tho];
27                     else if (tho == len2) rightMargin = nums1[mid];
28                     else rightMargin = min(nums1[mid], nums2[tho]);
29                     if (cand1 > cand2)
30                         return (double)(cand1 + rightMargin) / 2.0;
31                     return (double)(cand2 + rightMargin) / 2.0;
32                 }
33             }
34         }
35     }
36 };