文章目录

• 中位数
• 一个序列的中位数
• 两个序列的中位数
• 合并序列找到中位数
• 不合并序列
• 基本思想
• C++实现

中位数

对于一个有序序列来说，很简单，如果长度为 $n$n 的话，那么中位数就是序列中 $n/2$n/2 位置的数组元素了

一个序列的中位数

如果：

• 这是一个有序的序列，那么非常简单，不再多说
• 如果这不是一个有序序列，那么我们自然会这样想：先对序列进行排序再找到中位数，而这样的算法的复杂度其实就是排序算法的复杂度了（可以考虑快速排序，或者是用一个大小为序列大小一半的堆进行堆排序）

两个序列的中位数

合并序列找到中位数

如果我们希望找到两个有序序列的中位数的话，很快我们就可以想到，merge lists then find the median，将两个序列合并然后再找到中位数，这样的算法的复杂度自然就是序列合并算法的复杂度了，设两个序列的长度分别为m和n：
$O(N) = O(min(m, n)) \tag{0}$O(N)=O(min(m,n))(0)
显然，这样的算法的复杂度就是 $O(n)$O(n)，n的一次方的复杂度。这样我们自然会想到：我们能不能想到一个算法的复杂度是 $\log{n}$logn 呢？答案是肯定的。

不合并序列

基本思想

分别找到两个序列 $A,B$A,B 的中位数$a,b$a,b，然后：

• 如果 $a=b$a=b ，则这个值即所求中位数
  这是很好理解的，如果两个序列的中位数相同，那么合并的升序序列的中间依然会是这两个数，所以这就是所求中位数
• 如果 $a>b$a>b ，则保留 $A$A 的前半段和 $B$B 的后半段
  合并的升序序列的中位数必然在这两段之中。如果不在，假设中位数 $c$c 在A的后半段，那么，$c$c 一定大于A的前半段的所有元素，并且大于B的前半段的所有元素，也就是说， 此时 $c$c 的值已经大于合并序列的一半元素了，再加上 $a,b$a,b 这两个元素，那么，$c$c 至少大于合并序列一半以上的元素，不符合中位数的定义。同理在 $B$B 的前半段我们也可以这样证明
• 否则，$a &lt; b$a<b ，则保留 $A$A 的后半段和 $B$B 的前半段

重复以上过程，直到两个序列都只剩下一个元素，较小的一个即为中位数。

C++实现

我们还需要注意的是序列长度的奇偶性（partiality），我们需要根据序列长度确定是否要保留原来序列的中间点。
对于偶数，你可以简单的考虑剩下两个元素的情况，这个时候中间点就是第一个元素，那么自然的：

• 如果要保留前半段，那么肯定得包含中位数，否则前半段为空了，而此时我们肯定希望保留剩下一个元素，所以此时必须包括中间点
• 如果要保留后半段，那么自然就是不包括中间点了
  而对于奇数，很显然我们必须保留中间点，因为它仍有可能是最终的中位数，所以不管是前半段还是后半段都要保留中间点。

// ptr for starts and ends during the very iteration
int start_A = 0, end_A = length - 1, start_B = 0, end_B = length - 1;
int median_A = 0, median_B = 0;
// iterations
while(start_A != end_B && start_B != end_B){
	// get medians' position
	median_A = (start_A + end_A) / 2;
	median_B = (start_B + end_B) / 2;
	if(A[median_A] == B[median_B]){
		std::cout << A[median_A] << std::endl;
	}
	else if(A[median_A] > B[median_B]){
		if((end_A - start_A)%2 == 0){
			end_A = median_A;
			start_B = median_B + 1;
		}
		else{
			end_A = median_A;
			start_B = median_B;
		}
	}
	else{
		if((end_A - start_A)%2 == 0){
			end_B = median_B;
			start_A = median_A + 1;
		}
		else{
			end_B = median_B;
			start_A = median_A + 1;
		}
	}
}
std::cout << A[median_A] <= B[median_B]?A[median_A]:B[median_B] << std::endl;