问题描述：

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

样例1：

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

样例2：

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

看到这道题我就想到了归并排序中归并的过程，比较智障的是我没注意到题目给的是两个已排序的数组，我还用快排去排序了...

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {    int arr[10000];    int i=0,j=0,k=0,mid;    while(k<nums1Size+nums2Size&&i<nums1Size&&j<nums2Size)        arr[k++]=(nums1[i]<=nums2[j])?(nums1[i++]):nums2[j++];    if(i>=nums1Size){        while(j<nums2Size)            arr[k++]=nums2[j++];    }    else if(j>=nums2Size){        while(i<nums1Size)            arr[k++]=nums1[i++];    }    mid=(nums1Size+nums2Size)/2;    return (nums1Size+nums2Size)%2==0?(double)(arr[mid]+arr[mid-1])/2:(double)arr[mid];}

这应该算是比较naive的算法了，把两个有序数组合为一个有序数组，再输出这个数组的中位数。

这个算法是O(max(m,n))的复杂度，显然不是出题人想要的O(log(m+n))。

不知道如何写出O(log(m+n))的算法，于是我看了下LeetCode的讨论区，有了一点灵感。

要求有序数组A和B的中位数，还是得把A和B重新划分为数组a和b，并且要做到a和b大小相同，且a中元素小于等于b中元素，这样剩下的那个元素或者a中最大元素与b中最小元素的算数平均数就是要求的中位数。关键是如何划分得到数组a和b呢，把A和B合并为一个新数组是一种划分的办法，不过太慢了。可以用i将A划分为[0,i)和剩余两部分，同样用j将A划分为[0,j)和剩余两部分。a和b分别由新划分得到的四个部分中的两个部分组成。确切地说a由A[0,i)和B[0,j)组成，b由剩余部分组成。因为a和b大小要相同，所以i+j==(m+n)/2，即j==(m+n)/2-i，所以现在问题变成了求i使得i满足A[i-1]<=B[j]&&B[j-1]<=A[i]，其中j为(m+n)/2-i。（值得一提的是，m+n是奇是偶并不影响划分，因为(m+n)/2会自动舍位）

这时候原问题就变成了一个查找问题，因为数组已被排序，果断二分查找啊。

Median of Two Sorted Arrays问题