# 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数

@TOC

## # 题目描述

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

You may assume `nums1` and `nums2` cannot be both empty.

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
``````

## # 解题方法

### # 二分查找

C++代码如下：

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int M = nums1.size();
int N = nums2.size();
if (M > N) return findMedianSortedArrays(nums2, nums1);
int L = M + N;
int k = (L + 1) / 2; //总共左边需要多少个元素
int l = 0, r = M; // 对于nums1而言
int m1 = 0, m2 = 0;
while (l < r) {
m1 = l + (r - l) / 2; // nums1的分割位置，左边的元素个数
m2 = k - m1; // nums2的分割位置，左边的元素个数
if (nums1[m1] < nums2[m2 - 1]) {
l = m1 + 1;
} else {
r = m1;
}
}
m1 = l;
m2 = k - l;
double c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1],
m2 <= 0 ? INT_MIN : nums2[m2 - 1]);
if (L & 1)
return c1;
double c2 = min(m1 >= M ? INT_MAX : nums1[m1],
m2 >= N ? INT_MAX : nums2[m2]);
return (c1 + c2 ) / 2;
}
};
``````

## # 日期

2019 年 9 月 15 日 —— 中秋假期的最后一天啦，刷题加油~