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

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
題意：
給出兩個遞增序列，求該兩個遞增序列合并后的中位數。
我的答案：
第一次做的時候，其實跟最佳答案很相近了。
對左邊數組進行二分，找到二分位置的數字，然后用二分查找到右邊數組查找這個數字的位置，然后判斷兩邊元素個數是否相等。
最佳答案：
為了做這道題，我們需要去理解“中位數”. 在統計中, 在統計,中位數是用來將一組分成兩個相等的長度子集,
其中一個子集每個元素總是大于等于另一個子集元素。如果我們理解的使用值劃分,我們非常接近答案。
首先我讓A根據一個隨機位置i來分成兩個部分。
      left_A             |        right_AA[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
因為有m個元素,所以有m + 1種(i = 0 ~ m)。我們知道:len(left_A)=i,len(right_A)= m - i。
注意:當i= 0,left_A是空的,當i= m,right_A是空的。
同樣的方法，我讓B根據一個隨機位置j來分成兩個部分
      left_B             |        right_BB[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
把left_A，left_B為一組,把right_A，right_B到另一組,我們的名字他們left_part，right_part:
      left_part          |        right_partA[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
如果我們可以保證：
1) len(left_part) == len(right_part)2) max(left_part) <= min(right_part)
然后我們把所有元素以同樣的長度分成兩個部分進入left_part,right_part,然后其中一個part始終要大于等于另一個。
然后，median = (max(left_part) + min(right_part))/2.
為了確保這兩個條件,我們只需要確保:
(1) i + j == m - i + n - j (or: m - i + n - j + 1)    if n >= m, we just need to set: i = 0 ~ m, j = (m + n + 1)/2 - i(2) B[j-1] <= A[i] and A[i-1] <= B[j]
細節不予多說了。
注意：part存在空集的情況。
代碼：
class Solution {public:    double findMedianSortedArrays(vector<int> nums1, vector<int> nums2) {        int num = (nums1.size() + nums2.size() + 1) / 2;        if(nums1.size() > nums2.size()) nums1.swap(nums2);        if(nums1.size() == 0 && nums2.size() == 1) return nums2[0];        int num1 = nums1.size(),num2 = nums2.size();        int l = 0,r = nums1.size(),mid;        int mx,mi;        while(l<=r)        {            mid = (l+r)/2;            int rest = num - mid;            if(rest < 0){                r = mid - 1;continue;            }else if(rest > num2){                l = mid + 1;continue;            }            if(mid != 0 && rest == 0) mx = nums1[mid-1];            else if(mid == 0 && rest != 0) mx = nums2[rest-1];            else mx = max(nums1[mid-1],nums2[rest-1]);            if(mid != num1 && rest == num2) mi = nums1[mid];            else if(mid == num1 && rest != num2) mi = nums2[rest];            else mi = min(nums1[mid],nums2[rest]);            if(mx <= mi){                l = mid;                break ;            }            if(mid == 0){                l = mid + 1;            }else if(rest == 0){                r = mid - 1;            }else{                if(mx == nums1[mid-1])                    r = mid - 1;                else                    l = mid + 1;            }        }        if((num1+num2)%2){            return mx;        }else{            return (mi+mx)/2.0;        }    }};