问题回顾

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

---

步骤一：问题分析与直觉

目标：找到两个有序数组合并后的中位数，要求时间复杂度为O(log(m + n))。

关键观察：

1. 中位数定义：将合并后的数组分为左右两部分，左边所有元素 ≤ 右边所有元素，且左半部分长度与右半部分相等或大1。
2. 分割点性质：若找到分割点使得左半部分的最大值 ≤ 右半部分的最小值，则中位数由这两个值决定。

---

步骤二：算法设计

1. 确保较短的数组进行二分查找

• 交换数组，使nums1是较短的数组。这可以优化时间复杂度至O(log(min(m, n)))。

2. 确定分割点

• 定义i为nums1的分割点，j为nums2的分割点，满足：

  i + j = (m + n + 1) / 2
  

• 左半部分包含nums1[0..i-1]和nums2[0..j-1]，右半部分包含nums1[i..m-1]和nums2[j..n-1]。

3. 边界条件处理

• 当i=0时：nums1的左半部分为空 → nums1LeftMax = INT_MIN。
• 当i=m时：nums1的右半部分为空 → nums1RightMin = INT_MAX。
• 当j=0时：nums2的左半部分为空 → nums2LeftMax = INT_MIN。
• 当j=n时：nums2的右半部分为空 → nums2RightMin = INT_MAX。

4. 调整分割点的条件

• 正确分割的条件：

  nums1LeftMax ≤ nums2RightMin 且 nums2LeftMax ≤ nums1RightMin
  

• 条件不满足时的调整：
  • 若nums1LeftMax > nums2RightMin：说明i太大，需减小 → high = i - 1。
  • 若nums2LeftMax > nums1RightMin：说明i太小，需增大 → low = i + 1。

5. 计算中位数

• 总长度为奇数：中位数为左半部分的最大值max(nums1LeftMax, nums2LeftMax)。
• 总长度为偶数：中位数为(max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2.0。

---

步骤三：代码实现与注释

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if(nums1.size()>nums2.size())//这里始终保证nums1是更小的数组 避免接下来数组越界。
    {
        return findMedianSortedArrays(nums2,nums1);
    }
    int m = nums1.size(),n = nums2.size(),totalleft = (m+n+1)/2; //左半部分总元素数 数组元素数量为奇数的时候就是中间数
    int low = 0,high=m;
    while(low<=high)
    {
        int i = (low+high)/2;
        int j = totalleft - i;
        //处理边界条件
        int nums1LeftMax = (i==0)?INT_MIN:nums1[i-1];
        int nums1RightMin = (i==m)?INT_MAX:nums1[i];
        int nums2LeftMax = (j==0)?INT_MIN:nums2[j-1];
        int nums2RightMin = (j==n)?INT_MAX:nums2[j];
        //进入正常条件判断
        if(nums1LeftMax<=nums2RightMin && nums2LeftMax <= nums1RightMin)
        {
            if((m+n)%2 == 1)//合并数组元素为奇数个
              {return max(nums1LeftMax,nums2LeftMax);}
              else{
                return (min(nums1RightMin,nums2RightMin) +max(nums1LeftMax,nums2LeftMax) )/2.0;//这里如果不写2.0写2会输出整数
              }
        }else if(nums1LeftMax>nums2RightMin){
            high--;//high = i-1也可
        }else{
            low++;//low = i+1也可
        }
    }
    return 0;//不会返回值 纯为了语法要求
    }
};

---

步骤四：示例推演

示例1：nums1 = [1, 3], nums2 = [2]

1. 初始化：m=2, n=1, totalLeft=(3+1)/2=2。
2. 二分查找：
   • low=0, high=2 → i=1, j=1.
   • nums1LeftMax=1, nums1RightMin=3, nums2LeftMax=2, nums2RightMin=INT_MAX.
   • 满足条件1 ≤ INT_MAX且2 ≤ 3 → 中位数为max(1,2)=2。

示例2：nums1 = [1, 2], nums2 = [3, 4]

1. 初始化：m=2, n=2, totalLeft=(4+1)/2=2.
2. 二分查找：
   • low=0, high=2 → i=1, j=1.
   • nums1LeftMax=2, nums1RightMin=INT_MAX, nums2LeftMax=3, nums2RightMin=4.
   • 不满足条件（3 > 2） → 调整low=2。
   • i=2, j=0 → nums1LeftMax=2, nums1RightMin=INT_MAX, nums2LeftMax=INT_MIN, nums2RightMin=3.
   • 满足条件 → 中位数为(2 + 3)/2 = 2.5。

---

步骤五：复杂度分析

• 时间复杂度：O(log(min(m, n)))，二分查找仅在较短的数组上进行。
• 空间复杂度：O(1)，仅使用常量额外空间。

---

总结

通过将问题转化为寻找满足条件的分割点，并利用二分查找优化搜索过程，我们可以在对数时间内高效解决两个有序数组的中位数查找问题。该算法的关键在于正确处理边界条件，并利用数学性质快速调整分割点位置。

思考1：为什么满足nums1LeftMax ≤ nums2RightMin 且 nums2LeftMax ≤ nums1RightMin 就是正确分割 为什么两个分开的数组满足这个条件 他们合并之后的数组的中位数就满足条件？

核心思路

1. 问题转化：
   中位数的本质是将数组分割为左半部分和右半部分，左半部分的最大值 $\le$ 右半部分的最小值。若两个数组的合并长度为偶数，则中位数为左半部分的最大值与右半部分的最小值的平均；若为奇数，则中位数为左半部分的最大值。

2. 分割点的定义：
   在较短数组 nums1 中确定一个分割点 i，将数组分为左半部分 nums1[0..i-1] 和右半部分 nums1[i..m-1]。根据总左半部分元素数 totalLeft = (m + n + 1) // 2，另一数组 nums2 的分割点 j 满足 j = totalLeft - i。

3. 分割条件的验证：
   当满足以下条件时，分割点有效：

   • nums1LeftMax（nums1 左半部分的最大值） $\le$ nums2RightMin（nums2 右半部分的最小值）
   • nums2LeftMax（nums2 左半部分的最大值） $\le$ nums1RightMin（nums1 右半部分的最小值）

   此时，合并后的左半部分最大值和右半部分最小值即可确定中位数 。

---

为什么条件成立即为正确分割？

1. 分割的意义：
   分割后的左半部分包含 i + j 个元素，右半部分包含剩余元素。若两个左半部分的最大值均不超过对方右半部分的最小值，则说明合并后的数组在此处自然分割，左半部分的所有元素 $\le$ 右半部分的所有元素，满足有序数组的性质 。

2. 合并后的中位数位置：
   中位数位于分割点处。例如：

   • 若总长度为奇数，中位数是左半部分的最大值（即 max(nums1LeftMax, nums2LeftMax)）。
   • 若总长度为偶数，中位数为左半最大值与右半最小值的平均（即 (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2）。

---

算法步骤

1. 预处理：确保 nums1 是较短的数组，以优化二分次数 。
2. 二分查找：在 nums1 的索引范围 [0, m] 内进行二分：
   • 计算分割点 i 和 j，处理边界（如 i=0 或 i=m 时用极小/极大值替代）。
   • 检查分割条件：根据条件调整二分边界，直到找到满足条件的分割点。
3. 计算中位数：根据奇偶性和分割点的边界值计算结果 。

---

复杂度分析

• 时间复杂度：二分查找的范围是较短的数组，复杂度为 $O(\log (\min (m,n)))$，满足 $O(\log (m+n))$ 的要求 。
• 空间复杂度：$O(1)$，仅使用常数空间。

---

示例验证

• 示例1：nums1 = [1,3]，nums2 = [2]：

  • totalLeft = (2+1+1)/2 = 2，i=1，j=1。
  • 分割后左半部分为 [1] 和 [2]（最大值 2），右半部分为 [3]，满足条件，中位数为 2 。

• 示例2：nums1 = [1,2]，nums2 = [3,4]：

  • totalLeft = (2+2+1)/2 = 2，i=1，j=1。
  • 左半部分为 [1] 和 [3]（最大值 3），右半部分为 [2]（最小值 2）和 [4]，中位数为 (3+2)/2 = 2.5 。

通过二分查找分割点，并验证两个左半部分的最大值不超过对方右半部分的最小值，可以高效定位合并后的中位数，避免了合并数组的开销。这一方法的关键在于利用有序数组的性质，将全局问题转化为局部条件的验证 。

---

思考2：为什么在这个过程中必须确保nums1是较小的数组？

下面我将详细解释整个算法的思路，并重点说明为什么必须保证在二分查找过程中选择较短的数组（即确保 nums1 的长度不大于 nums2 的长度），如果删除下面这段代码：

if (nums1.size() > nums2.size()) {
    return findMedianSortedArrays(nums2, nums1);
}

程序就可能无法正常工作。

---

一、算法思路详细解析

1. 问题描述

给定两个**正序（从小到大）**数组 nums1 和 nums2，长度分别为 m 和 n。要求在时间复杂度 O(log (m+n)) 内求出合并后数组的中位数，而不实际合并两个数组。

中位数的定义：

• 当两个数组合并后的总元素个数为奇数时，中位数是左半部分（较小那边）最大的元素；
• 当总元素个数为偶数时，中位数是左半部分最大值与右半部分最小值的平均数。

---

2. 分割思想

为了达到 O(log (m+n)) 的时间复杂度，我们使用二分查找的思想。关键在于将两个数组“虚拟地”合并后分成左右两部分，要求：

• 左半部分包含 (m + n + 1) / 2 个元素（保证在奇数时左半部分比右半部分多一个），
• 右半部分包含剩余的元素。

设定：

• 在 nums1 中取分割点 i（即 nums1 的前 i 个元素在左半部分），
• 在 nums2 中取分割点 j，使得
  [
  i + j = \text{totalLeft} = \frac{m + n + 1}{2}
  ]

因此，j = totalLeft - i。

---

3. 分割点正确性的条件

为了保证左半部分所有元素都不大于右半部分所有元素，我们需要满足以下两个条件：

• 条件1： nums1 左半部分的最大值 ≤ nums2 右半部分的最小值
  即：
  [
  \text{nums1LeftMax} \leq \text{nums2RightMin}
  ]
  其中：

  • nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1]
  • nums2RightMin = (j == n) ? INT_MAX : nums2[j]

• 条件2： nums2 左半部分的最大值 ≤ nums1 右半部分的最小值
  即：
  [
  \text{nums2LeftMax} \leq \text{nums1RightMin}
  ]
  其中：

  • nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1]
  • nums1RightMin = (i == m) ? INT_MAX : nums1[i]

如果同时满足这两个条件，就找到了正确的分割点，此时：

• 如果 (m + n) 为奇数，则中位数为：
  max(nums1LeftMax,nums2LeftMax)
• 如果 (m + n) 为偶数，则中位数为：
  (min(nums1RightMin,nums2RightMin) +max(nums1LeftMax,nums2LeftMax) )/2.0
  注意这里不能写成/2，要写/2.0不然返回的int结果不会保留小数

---

4. 二分查找过程

由于我们需要在一个数组中二分查找正确的分割点，我们选择对 nums1 进行二分查找。设 nums1 的长度为 m，那么 i 的取值范围就是 0 到 m。每次：

• 计算 i = (low + high) / 2，
• 计算 j = totalLeft - i。

接下来检查上面所述的两个条件：

• 如果 nums1[i-1] > nums2[j]，说明 i 太大（也就是说，nums1 的左侧有太多大的数），需要减小 i，因此将 high = i - 1。
• 否则（nums2[j-1] > nums1[i]），说明 i 太小，需要增大 i，因此将 low = i + 1。

通过不断调整 low 和 high，最终能找到满足条件的 i 和 j。

---

二、为什么必须确保 nums1 是较小的数组？

1. 保证二分查找的边界正确

• 分割索引范围：
  在算法中，我们对 nums1 进行二分查找，令 i 的取值范围为 0 到 m。同时，j = totalLeft - i 的值需要满足 0 <= j <= n。
  如果 nums1 比 nums2 长（即 m > n），则可能出现以下问题：
  • 当 i 取某些值时，计算出来的 j 可能为负数或超过 nums2 的长度，从而导致数组越界，条件检查（如 nums2[j - 1] 或 nums2[j]）时出错。

2. 保证搜索空间最小、效率最高

• 时间复杂度：
  二分查找的时间复杂度是 O(log(搜索空间的大小))。
  选择较小的数组作为搜索对象，搜索空间为 O(log(min(m, n)))，这不仅符合题目要求，还能使搜索过程更加高效。如果不保证这一点，可能在最坏情况下搜索空间会增大。

3. 代码中的处理

代码中最开始的这段判断：

if (nums1.size() > nums2.size()) {
    return findMedianSortedArrays(nums2, nums1);
}

的作用就是：

• 如果 nums1 的长度大于 nums2，就交换两个数组，使得接下来的二分查找总是在较小的数组上进行。

删除这段代码后会出现的问题：

• 若 nums1 较长，则 i 的取值范围（0 到 m）可能导致计算出的 j = totalLeft - i 超出 nums2 的合法范围（比如负值或者大于 n），进而导致在访问 nums2[j-1] 或 nums2[j] 时发生越界错误。
• 逻辑判断也可能不成立，导致无法正确收敛到满足条件的分割点，最终结果不正确或程序崩溃。

---

三、总结

1. 算法整体思路：

   • 通过二分查找在较短的数组 nums1 上寻找分割点 i，并根据 i 计算 nums2 的分割点 j（使得左右两边元素个数满足要求）。
   • 利用四个关键值（nums1LeftMax、nums1RightMin、nums2LeftMax、nums2RightMin）判断分割是否合理。
   • 根据总元素个数奇偶性计算中位数。

2. 为什么必须确保 nums1 是较小的数组？

   • 边界问题： 保证二分查找时 i 的范围是 0 到 m，同时能使得计算出的 j = totalLeft - i 落在 [0, n] 范围内，避免数组越界。
   • 搜索效率： 限制二分查找在较小的数组中进行，可以使搜索空间更小，算法效率更高。
   • 逻辑正确性： 如果不交换，可能因 j 的计算出错导致条件判断失败，从而使得算法无法找到正确的分割点，最终得到错误结果或程序崩溃。

因此，这段代码确保 nums1 是较小的数组是整个算法正确性和鲁棒性的关键。如果删除这部分代码，程序就不能正常工作，原因正是在于可能会导致分割点计算中 j 超出合法范围，破坏后续逻辑判断。

---

思考3：nums1RightMin = (i == m) ? INT_MAX : nums1[i]中的INT_MAX换成INT_MIN有没有影响？

在这一行代码中：

int nums1RightMin = (i == m) ? INT_MAX : nums1[i];

使用 INT_MAX 的目的是为了在 nums1 的右侧没有元素时，提供一个“无限大”的占位值。具体原因如下：

1. 代表“无穷大”
   当 i == m 时，说明 nums1 中所有的元素都在左侧，右侧实际上为空。为了保证在后续的比较中不影响结果，我们需要一个不可能成为最小值的数字，这时使用 INT_MAX（最大的整数）作为右侧的“虚拟”最小值。这样在取两边的最小值时：

   min(nums1RightMin, nums2RightMin)
   

   如果 nums1RightMin 为 INT_MAX，则结果完全由 nums2RightMin 决定，不会错误地影响中位数计算。

2. 如果换成 INT_MIN，会产生问题
   如果将其替换为 INT_MIN（最小的整数），则当 i == m 时，nums1 右侧的“最小值”就会是一个非常小的值。这样，在后续计算中，例如：

   min(nums1RightMin, nums2RightMin)
   

   如果 nums1RightMin 为 INT_MIN，那么无论 nums2RightMin 有多大，min 函数都会返回 INT_MIN。这显然与实际情况不符，也会导致分割点判断以及最终中位数计算出现错误。

举个例子说明

假设：

• nums1 = [1, 2]，m = 2
• nums2 = [3, 4, 5]，n = 3

如果在某个分割点，恰好 i == m（即 i == 2），那么按照正确的代码：

• nums1RightMin = INT_MAX
• 这样，在比较时，只要 nums2RightMin 是有效的数字，就会选用 min(INT_MAX, nums2RightMin) = nums2RightMin。

而如果错误地使用 INT_MIN：

• nums1RightMin = INT_MIN
• 那么 min(INT_MIN, nums2RightMin) 就会始终得到 INT_MIN，完全破坏后续逻辑，使得正确的分割条件无法满足，从而导致错误的中位数计算。

总结

不能将 INT_MAX 替换为 INT_MIN。

• INT_MAX 在这里代表“右侧没有元素时的一个无限大值”，这样在后续比较时不会干扰到结果。
• 使用 INT_MIN 会使得右侧的最小值错误地变成了一个非常小的数，破坏了分割点判断和中位数计算的正确性。