编程开发Median of Two Sorted Arrays

Description

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

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

Analyse

俗话说，描述越简单的题目越难，这里也属于一题。题意很简单，找到两个有序数列中的中位数，要是题目的描述到这就结束的话，只需一个归并，题目就做完了。时间复杂度为O（m+n），但是问题就在这里，题目要求时间复杂度为O（log（m+n）），这也是这道题被划分为Hard的原因。看到log，我们很容易 想到二分法，问题是怎么把二分法用到这个问题上来，然后我们还发现了题目还有一个条件没用上，就是“有序”，也许把这两个条件加起来，就能获得答案了呢。
算法如下：
我们设那两个数列一个为A，一个为B。
我们在A的任意位置i将A划分为两部分

同理，我们在B的任意位置j将B划分为两部分

然后我们把A和B的左半部分放在一块，A和B的右半部分放在一块。

若我们能使得left_part和right_part的长度一样且max(left_part)<=min(right_part)，那么右边的数都大于左边的数且数量一样，中位数就等于(max(left_part)+min(right_part))/2。
对于前面两个条件，我们可以转换为代码。
(1)i+j==m-i+n-j(或者i+j==m-i+n-j+1) 即：当n>=m时，i=0~m，j=(m+n+1)/2-i
(2)B[j-1]<=A[i] && A[i-1]<=B[j]。
(1)处的n>=m是用来保证j一直大于0，这里可以通过比较两个数列来保证。
现在重点需要考虑的是(2)的边界问题，当i=0/j=0/i=m/j=n时，上面的公式会出问题的，不过我们先不考虑这一点。
i的取值可以通过二分查找来获得。
让imin=0，imax=m，i=(imin+imax)/2，j=(m+n+1)/2-i。
a.当B[j-1]<=A[i] && A[i-1]<=B[j]时，找到了答案，退出二分查找
b.当B[j-1]>A[i]时，表示A[i]太小了，所以需要变大，所以i需要往大的找，此时，j会变小，B[j-1]也会变小，即：imin=i+1。
c.当A[i-1]>B[j]时，表示A[i-1]太大了，所以需要变小，所以i需要往小的找，此时，j会表大，B[j]也会变大，即：imax=i-1。
当二分查找退出时，我们找到了答案。中位数为：
max(A[i-1], B[j-1]) (当m+n为奇数时)，(max(A[i-1], B[j-1]) + min(A[i], B[j]))/2 (当m+n为偶数时)。
我们再回来考虑边界的问题，我们可以发现，若i，j取到边界时，中位数就找到了，因为中位数存在于其中某个数列里面，我们只需要把边界挑出来就好了。
a.(j == 0 || i == m || B[j-1] <= A[i]) && (i == 0 || j = n || A[i-1] <= B[j])即找到答案。
然后强化后两个条件。
b.j > 0 && i < m && B[j - 1] > A[i]，我们可以证明j > 0 和 i < m时等价的，所以只需要：j > 0 && B[j - 1] > A[i]即可，imin=i+1。
c.i > 0 && j < n && A[i - 1] > B[j]，同上，i > 0 和 j < n也是等价的，所以只要j < n && A[i - 1] > B[j]即可，imax=i-1。
算法结束。时间复杂度为O(log(min(m,n)))。

Code

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        vector temp;
        if (nums1.size()>nums2.size()) {
            temp=nums1;nums1=nums2;nums2=temp;
        }
        int m=nums1.size(),n=nums2.size();
        int min=0,max=m,mid=(m+n+1)/2,max_left,min_right;
        while (min<=max) {
            int i,j;
            i=(min+max)/2;
            j=mid-i;
            if (inums1[i]) {
                min=i+1;
            } else {
                if (i>0 && nums1[i-1]>nums2[j]) {
                    max=i-1;
                } else {
                    if (i==0) {
                        max_left=nums2[j-1];
                    } else {
                        if (j==0) {
                            max_left=nums1[i-1];
                        } else {
                            if (nums1[i-1]>nums2[j-1]) max_left=nums1[i-1];
                            else max_left=nums2[j-1];
                        }
                    }
                    if ((m+n)%2==1) return max_left;
                    if (i==m) {
                        min_right=nums2[j];
                    } else {
                        if (j==n) {
                            min_right=nums1[i];
                        } else {
                            if (nums1[i]