方法一：二路归并

两个升序数组可以使用双指针的方式在$O(n)$的时间内归并为一个升序的大数组，已知个数，可以直接求出中位数。

方法二：快速选择

求中位数相当于求第k大的数，对于一个数组求第k大的数可以用快速选择，时间复杂度$O(n)$，但是这里就没有用到两个数组有序的性质

方法三：分割线+二分，时间复杂度$O(log(min(m, n)))$

官方题解视频链接：【4. 寻找两个正序数组的中位数 Median of Two Sorted Arrays 【LeetCode 力扣官方题解】】https://www.bilibili.com/video/BV1Xv411z76J?vd_source=50714aba974e807c499d6a482d48a437

在一个一维数组里，我们可以使用分割线求中位数，如果是偶数，分割线左右元素个数相等，左边均<=右边，这样（左边最大的数+右边最小的数）/ 2.0就是中位数，如果是奇数，可以规定左边元素比右边元素多一个，左边均<=右边，这样左边最大的元素就是中位数。

对于两个数组，也可以画一条这样的分割线，如图，分割线左边均<=右边，偶数奇数情况与上面相同。由于两个数组都是升序，所以对于分割线左边均<=右边这个条件，我们只需要保证A[i – 1] <= B[j]，B[j – 1] <= A[i]，（i，j表示第一个和第二个数组分割线后面一个元素的下标，这样i，j还可以表示第一个和第二个数组分割线左边元素个数）对于第一个数组，i的取值范围是[0，nums1Size]，注意两个边界，对于第二个数组，j的取值范围是[0，nums2Size]，我们可以二分得出较小数组的分割线i的位置，对于每个i，j都是确定的，因为j = 分割线左边元素总个数 – i。二分方法：较小数组可以根据性质：A[i – 1] <= B[j]，分为两部分，左边满足这个性质，右边不满足，左边和右边区间就是由分割线分割开的，可以求左边区间的最右边的端点，加一就是分割线的位置i。求出i后，还要注意特殊处理特殊情况防止数组访问越界。

int max(int a, int b){return a > b ? a : b;}
int min(int a,int b){return a < b ? a : b;}
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    if(nums1Size > nums2Size){
        int *temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        swap(&nums1Size, &nums2Size);
    }
    int l = 0, r = nums1Size;
    int leftSum = nums1Size + nums2Size + 1 >> 1;
    while(l < r){
        int mid1 = l + r + 1 >> 1;
        int mid2 = leftSum - mid1;
        if(nums1[mid1 - 1] <= nums2[mid2])l = mid1;
        else r = mid1 - 1;
    }
    if((nums1Size + nums2Size) % 2 == 1){
        if(l - 1 >= 0 && leftSum - l - 1 >= 0)return max(nums1[l - 1], nums2[leftSum - l - 1]);
        else if(l - 1 >= 0)return nums1[l - 1];
        else return nums2[leftSum - l - 1];
    } else {
        int leftMax, rightMin;
        if(l - 1 >= 0 && leftSum - l - 1 >= 0)leftMax = max(nums1[l - 1], nums2[leftSum - l - 1]);
        else if(l - 1 >= 0)leftMax = nums1[l - 1];
        else leftMax = nums2[leftSum - l - 1];
        if(l < nums1Size && leftSum - l < nums2Size)rightMin = min(nums1[l], nums2[leftSum - l]);
        else if(l < nums1Size)rightMin = nums1[l];
        else rightMin = nums2[leftSum - l];
        return (leftMax + rightMin)/2.0;
    }
}