两有序数组合并后第k小元素算法正确性及复杂度疑问

问题背景 #

给定两个有序数组A[1..m]、B[1..n]和整数k，需快速找到A∪B合并后的第k小元素（示例：A=[0,1,6,9,12,13,18,20]，B=[2,5,7,17,19]，k=6时返回7）。

已有的解决方案包含两个算法：

1. 等长有序数组合并中位数算法（Median） #

Median(A[1 .. n], B[1...n]) :
  if n < 100:
    use brute force
  else if A[n/2] > B[n/2]:
    return Median(A[1 . . n/2], B[n/2 + 1 . . n])
  else
    return Median(A[n/2 + 1 . . n], B[1 . . n/2])

该算法的正确性已得到证明，时间复杂度为O(log(n))。

2. 基于Median的Select算法 #

（注：Median算法支持处理越界索引，越界位置用−∞或∞补值）

Select(A[1 .. m], B[1 .. n], k):
  if k < (m + n)/2
    return Median(A[1 .. k], B[1 .. k])
  else
    return Median(A[k−n .. m], B[k-m .. n])

疑问解答 #

疑问1：Select算法中为何使用[k−n .. m]和[k−m .. n]的边界？请给出正确性证明。 #

解答

这个边界的核心逻辑是提前排除不可能包含第k小元素的区间：

1. A数组的有效区间推导：
   假设第k小元素在A中的位置是i，那么B中至少要有k - i个元素小于等于它。由于B的总长度是n，因此k - i ≤ n，变形可得i ≥ k - n。同时i不能超过A的长度m，所以A的有效区间是[max(1, k−n), m]。算法中直接写[k−n .. m]是因为越界位置会用−∞补值，等价于从A的第一个元素开始。
2. B数组的有效区间推导：
   同理，假设第k小元素在B中的位置是j，则A中至少要有k - j个元素小于等于它，即k - j ≤ m，变形得j ≥ k - m。同时j不能超过B的长度n，所以B的有效区间是[max(1, k−m), n]，越界位置补−∞。

正确性证明：
当k ≥ (m+n)/2时，我们要找的是合并数组中偏后的元素：

• 对于A中小于k−n的元素，即使所有B的元素都比它们大，这些元素的总数最多是(k−n−1) + n = k−1，达不到第k个位置，因此这些元素不可能是第k小元素，可以安全排除。
• 同理，B中小于k−m的元素，总数最多是(k−m−1) + m = k−1，同样可以排除。
• 剩下的A区间[k−n .. m]和B区间[k−m .. n]，它们的长度之和为(m - (k−n) + 1) + (n - (k−m) + 1) = 2*(m+n -k +1)。由于k ≥ (m+n)/2，m+n -k ≤ k，且通过补值可以让两个子数组长度相等，刚好适配Median算法——此时第k小元素等价于这个子合并数组的中位数。

疑问2：为何时间复杂度O(log(min{k, m + n − k}))等价于O(log(m + n))？ #

解答

我们分两种情况分析：

• 当k ≤ (m+n)/2时，min{k, m+n−k} = k，而k ≤ (m+n)/2，因此log(k) ≤ log((m+n)/2) = log(m+n) - log2。由于复杂度分析中忽略常数项，log(k)属于O(log(m+n))。
• 当k > (m+n)/2时，min{k, m+n−k} = m+n−k，而m+n−k < (m+n)/2，同理log(m+n−k) ≤ log((m+n)/2) = log(m+n) - log2，也属于O(log(m+n))。

本质上，min{k, m+n−k}的最大值是floor((m+n)/2)，它的对数与log(m+n)是同阶的——对数函数的增长特性决定了常数倍数和加减常数不会改变复杂度的阶，因此两者等价。

内容的提问来源于stack exchange，提问作者Hugh Mann