力扣经典二分题：4. 寻找两个正序数组的中位数

题目链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

一、题目分析

这道题目是让我们在两个正序的数组中寻找中位数
已知两个数组的大小分别是：int m = nums1.size(),n = nums2.size();
中位数性质1：中位数左侧元素 ≤ 中位数且中位数右侧元素 ≥ 中位数（以升序来看）
中位数性质2：对于一个长度为 N 的数组，中位数将数组一分为二，使得左侧与右侧得元素长度差 ≤ 1
当 m + n 为奇数时，我们需要找到合并后数组中第 k + 1 小的元素，其中 k = (m + n) / 2。
当 m + n 为偶数时，我们需要找到合并后数组中第 k 和第 k + 1 小的元素，然后计算它们的平均值，其中 k = (m + n) / 2 - 1（注意这里 k 是基于 0 的索引，所以实际要找的元素位置是 k 和 k + 1）。

二、算法原理讲解

解法一：暴力排序

通过合并排序的原理，通过中位数的性质，可快速得到中位数的下标，较为简单

时间复杂度为O(M+N)，空间复杂度为O(M+N)

解法二：双指针

时间复杂度为O(M+N)，空间复杂度为O(1)

解法三：暴力枚举

解法四：二分优化

三、编写代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        int m = nums1.size(), n = nums2.size();
        if(m > n) swap(nums1,nums2); // 保证nums1始终是较短数组

        int k = (m + n + 1) / 2; // 应划分给小数组的个数

        // 枚举 i [0,m]
        for(int i = 0;i <= m;i++)
        {
            int&& j = k - i;
            // 分割线周围的四个值
            int a = i == m ? INT_MAX :nums1[i];
            int b = i == 0 ? INT_MIN :nums1[i-1];
            cout << i << ' ' << j << endl;
            int c = j == n ? INT_MAX :nums2[j];
            int d = j == 0 ? INT_MIN :nums2[j-1];
            // 分割线是否合法
            if(b <= c && d <= a)
            {
                if((m + n) % 2 == 1) return max(b,d);
                else return (double)(max(b,d) + min(c,a)) / 2;
            }
        }
        return 1314.521;
    }
};

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        // 保证nums1始终是较短数组
        if(nums1.size() > nums2.size()) swap(nums1,nums2);

        // 应划分给小数组的个数
        int k = (nums1.size() + nums2.size() + 1) / 2; 

        // 枚举nums1数组中应该划分给小数组的元素个数（二分优化）
        int left = 0,right = nums1.size();
        while(left < right)
        {
            // mid ∈ [0,m]
            int i = (left + right + 1) / 2; 
            int j = k - i;
            cout << i << endl;


            if(nums1[i-1] <= nums2[j]) left = i;
            else right = i - 1;
        }
        
        // 分割线两边的值
        int a = left == nums1.size() ? INT_MAX :nums1[left];
        int b = left == 0 ? INT_MIN :nums1[left-1];
        int c = (k-left) == nums2.size() ? INT_MAX :nums2[k-left];
        int d = (k-left) == 0 ? INT_MIN :nums2[k-left-1];

        // 处理数据+返回
        if((nums1.size() + nums2.size()) % 2 == 1) return max(b,d);
        else return (double)(max(b,d) + min(c,a)) / 2;
    }
};