好的，我们这次来详细讲解 LeetCode 第 4 题「寻找两个正序数组的中位数」。
这是一道难度为 Hard 的题目，但它的思想非常重要，并且有多种解法，我会从最直观的解法开始，逐步深入到最优解。

1. 题目描述

给定两个大小分别为 m 和 n 的正序（非递减）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的 中位数 ，并且要求算法的时间复杂度为 O(log (m+n))。

示例 1：

nums1 = [1, 3]
nums2 = [2]
中位数是 2.0

示例 2：

nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3) / 2 = 2.5

2. 理解中位数的定义

对于一个有序数组：

• 如果长度 len 是奇数，中位数是下标为 len//2 的元素（从 0 开始计数）。
• 如果长度 len 是偶数，中位数是下标为 len//2 - 1 和 len//2 的两个元素的平均值。

对于两个数组合并后的情况：

• 总长度 L = m + n。
• 如果 L 是奇数，中位数是第 k = (L+1)//2 小的数（从 1 开始计数）。
• 如果 L 是偶数，中位数是第 k1 = L//2 小和第 k2 = L//2 + 1 小的两个数的平均值。

所以问题转化为：在两个有序数组中，找到第 k 小的数。

3. 解法 1：合并数组（O(m+n) 时间，O(m+n) 空间）

最直接的想法：把两个有序数组合并成一个有序数组，然后直接取中位数。

步骤：

1. 用两个指针分别指向两个数组开头。
2. 比较指针所指元素，将较小的放入新数组，移动指针。
3. 当某个数组遍历完后，将另一个数组剩余部分加入新数组。
4. 在新数组中根据奇偶取中位数。

缺点：时间复杂度 O(m+n)，空间复杂度 O(m+n)，不满足题目要求的 O(log(m+n))。

4. 解法 2：双指针找第 k 小（O(m+n) 时间，O(1) 空间）

我们不需要真的合并数组，只需模拟合并过程，用两个指针分别遍历两个数组，同时计数，找到第 k 小的元素。

步骤：

1. 设总长度 L = m + n，若 L 为奇数，找第 (L+1)//2 小的元素；若 L 为偶数，找第 L//2 和 L//2 + 1 小的元素，取平均。
2. 用两个指针 i（指向 nums1）、j（指向 nums2），初始为 0。
3. 用一个计数器 count 表示当前已遍历的元素个数。
4. 比较 nums1[i] 和 nums2[j]，将较小的元素对应的指针后移，count++。
5. 当 count == k 时，当前较小的元素就是第 k 小的数。

优点：空间 O(1)，但时间仍是 O(m+n)，不满足 O(log(m+n))。

5. 解法 3：二分查找（O(log(min(m, n)))）

为了达到 O(log(m+n))，必须用二分法。
实际上可以优化到 O(log(min(m, n)))。

核心思路：将找第 k 小问题转化为在两个数组中找合适的分割线，使得分割线左边的元素都小于等于右边的元素，并且左边元素个数等于 (m+n+1)//2。

5.1 模型建立

设数组 A（长度 m）和数组 B（长度 n），且假设 m ≤ n（否则交换，确保 A 是较短的数组）。

我们要在 A 中找一个位置 i（0 ≤ i ≤ m），在 B 中找一个位置 j，使得：

左半部分元素个数 = 右半部分元素个数（或左半部分多 1 个）

即：

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

并且满足：

A[i-1] ≤ B[j]  且  B[j-1] ≤ A[i]

这样，中位数就只与 max(A[i-1], B[j-1]) 和 min(A[i], B[j]) 有关。

5.2 二分查找 i 的过程

因为 m ≤ n，所以 i 的取值范围是 [0, m]。
对 i 进行二分搜索：

1. 设 i_min = 0, i_max = m。
2. 令 i = (i_min + i_max) // 2，j = (m + n + 1) // 2 - i。
3. 检查条件：
   • 如果 i > 0 且 A[i-1] > B[j]，说明 i 太大，需要减小 i（即 i_max = i - 1）。
   • 如果 i < m 且 B[j-1] > A[i]，说明 i 太小，需要增大 i（即 i_min = i + 1）。
   • 否则，i 是合适的。

5.3 找到分割后的中位数计算

找到正确的 i, j 后：

• 如果 (m + n) 是奇数，中位数 = max(A[i-1], B[j-1])。
• 如果 (m + n) 是偶数，中位数 = (max(A[i-1], B[j-1]) + min(A[i], B[j])) / 2.0。

注意边界情况：

• 如果 i == 0，表示 A 中所有元素都在右边，左边最大是 B[j-1]。
• 如果 j == 0，表示 B 中所有元素都在右边，左边最大是 A[i-1]。
• 如果 i == m，表示 A 中所有元素都在左边，右边最小是 B[j]。
• 如果 j == n，表示 B 中所有元素都在左边，右边最小是 A[i]。

5.4 举例说明

例：nums1 = [1, 3], nums2 = [2], m=2, n=1。

总长度 L=3 奇数，k=2（第 2 小的数）。

令 A=[1,3], B=[2], m=2, n=1。

二分 i 范围 [0,2]：

• i=1, j=(3+1)//2 - 1 = 1。
  检查：A[i-1]=1, B[j]=2 → 1 ≤ 2 ✅
  B[j-1]=B[0]=2, A[i]=3 → 2 ≤ 3 ✅
  分割正确。

左半部最大 = max(A[0], B[0]) = max(1,2) = 2。
中位数 = 2.0。

6. 代码框架（关键部分）

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    total_left = (m + n + 1) // 2
    
    low, high = 0, m
    while low <= high:
        i = (low + high) // 2
        j = total_left - i
        
        if i > 0 and nums1[i-1] > nums2[j]:
            high = i - 1
        elif i < m and nums2[j-1] > nums1[i]:
            low = i + 1
        else:
            # 找到合适分割
            if i == 0:
                max_left = nums2[j-1]
            elif j == 0:
                max_left = nums1[i-1]
            else:
                max_left = max(nums1[i-1], nums2[j-1])
            
            if (m + n) % 2 == 1:
                return max_left
            
            if i == m:
                min_right = nums2[j]
            elif j == n:
                min_right = nums1[i]
            else:
                min_right = min(nums1[i], nums2[j])
            
            return (max_left + min_right) / 2.0

7. 总结

• 中位数问题转化为两个有序数组的第 k 小问题。
• 暴力法 O(m+n) 不满足要求。
• 最优解用二分查找在较短数组上找分割点，达到 O(log(min(m, n))) 时间，O(1) 空间。
• 核心是确保分割后左右部分满足有序性，从而直接计算中位数。

需要我再用一个详细的例子一步步演示二分查找的过程吗？这样可以更直观地理解分割点的寻找。