好的，我们来看 LeetCode 第 4 题：“寻找两个正序数组的中位数”。

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 = m + n 是奇数，则中位数是第 (len+1)/2 个数（从 1 开始计数）。
• 如果是偶数，则中位数是第 len/2 个数与第 len/2 + 1 个数的平均值。

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

3. 直接合并的暴力方法（不符合要求）

最简单的方法：合并两个数组，然后直接取中位数。
合并需要 O(m+n) 时间，但题目要求 O(log(m+n))，所以不可行。

4. 转化为“找第 k 小的数”

假设我们要找第 k 小的数（k 从 1 开始计数）。

核心思路：比较两个数组的第 k/2 个元素（如果存在的话），小的那个数组的前 k/2 个元素一定不包含第 k 小的数，可以排除。

具体步骤（递归或迭代）：

1. 设我们要在两个数组 A 和 B 中找第 k 小的数。
2. 如果 A 的长度大于 B，交换它们，保证 A 是较短的数组（方便处理边界）。
3. 如果 A 为空，直接返回 B[k-1]。
4. 如果 k == 1，返回 min(A[0], B[0])。
5. 取 i = min(len(A), k/2)，j = min(len(B), k/2)。
6. 比较 A[i-1] 和 B[j-1]：
   • 如果 A[i-1] <= B[j-1]，说明 A[0..i-1] 都不可能是第 k 小的数，排除这 i 个元素，在 A[i:] 和 B 中找第 k-i 小的数。
   • 否则，排除 B[0..j-1]，在 A 和 B[j:] 中找第 k-j 小的数。

每次排除 k/2 个元素，所以复杂度是 O(log k)，而 k ≤ m+n，所以是 O(log(m+n))。

5. 中位数的 k 值设定

总长度 len = m + n：

• 若 len 为奇数：k = (len+1)/2，找一次即可。
• 若 len 为偶数：k1 = len/2，k2 = len/2 + 1，找两次（或一次找两个），然后取平均值。

6. 举例说明

以示例 2 为例：
nums1 = [1,2], nums2 = [3,4]，len = 4 为偶数，需要找第 2 小和第 3 小的数，然后取平均。

找第 2 小的数：

• k=2, A=[1,2], B=[3,4]
• i = min(2, 1) = 1, j = min(2, 1) = 1
• 比较 A[0]=1 与 B[0]=3，A[0] 较小，排除 A[0]，新数组 A’=[2], B=[3,4]，找第 k=1 小的数
• k=1 时，min(2,3)=2，所以第 2 小的数是 2。

找第 3 小的数：

• k=3, A=[1,2], B=[3,4]
• i = min(2, 1) = 1, j = min(2, 1) = 1
• 比较 A[0]=1 与 B[0]=3，A[0] 较小，排除 A[0]，A’=[2], B=[3,4]，找第 k=2 小的数
• 现在 k=2, A=[2], B=[3,4]
• i=min(1,1)=1, j=min(2,1)=1
• 比较 A[0]=2 与 B[0]=3，A[0] 较小，排除 A[0]，A’=[]，B=[3,4]，找第 k=1 小的数
• A 为空，返回 B[0]=3，所以第 3 小的数是 3。

中位数 = (2+3)/2 = 2.5。

7. 边界情况与细节

• 某个数组可能很短，甚至为空。
• 在取 k/2 时，如果某个数组长度不足 k/2，则取它的整个长度，这样另一个数组的前 k/2 个不可能全部被排除，保证正确性。
• 保证每次递归都能排除一部分元素，避免无限循环。

8. 代码思路（伪代码）

function findMedianSortedArrays(nums1, nums2):
    m = len(nums1), n = len(nums2)
    total = m + n
    if total % 2 == 1:
        return findKth(nums1, nums2, total // 2 + 1)
    else:
        left = findKth(nums1, nums2, total // 2)
        right = findKth(nums1, nums2, total // 2 + 1)
        return (left + right) / 2.0

function findKth(A, B, k):
    # 保证 A 是较短的数组
    if len(A) > len(B):
        return findKth(B, A, k)
    if len(A) == 0:
        return B[k-1]
    if k == 1:
        return min(A[0], B[0])
    
    i = min(len(A), k // 2)
    j = min(len(B), k // 2)
    
    if A[i-1] <= B[j-1]:
        return findKth(A[i:], B, k - i)
    else:
        return findKth(A, B[j:], k - j)

实际实现时可以用迭代代替递归，避免栈开销。

这样，我们就通过二分排除的方式，在 O(log(m+n)) 时间内解决了问题。