4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
法1：合并数组，排序，找中位数
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {nums1.insert(nums1.end(),nums2.begin(),nums2.end());sort(nums1.begin(), nums1.end());int total_size = nums1.size();return (total_size % 2 ==0 ) ? (nums1[total_size / 2] + nums1[total_size / 2 - 1]) / 2.0: nums1[total_size/ 2];}
};
法2：二分查找(ps:二分解题思路借鉴：灵茶山艾府 大佬)
class Solution {
public:double findMedianSortedArrays(vector<int>& a, vector<int>& b) {if (a.size() > b.size()) {swap(a, b);}int m = a.size(), n = b.size();a.insert(a.begin(), INT_MIN);b.insert(b.begin(), INT_MIN);a.push_back(INT_MAX);b.push_back(INT_MAX);int l = 0, r = m + 1;while (l + 1 < r) {int i = l + (r - l) / 2;int j = (m + n + 1) / 2 - i;if(a[i] <= b[j+1]){l = i;}else{r = i;}}int i = l;int j = (m + n + 1) / 2 - i;int max1 = max(a[i], b[j]);int min2 = min(a[i+1], b[j + 1]);return (m + n) % 2 ? max1 : (max1 + min2) / 2.0;}
};