问答题一个长度为L(L≥1)的升序序列S，处在第[L／2]个位置的数称为S的中位数。例如列S1=(11，13，15，17，19)，则S1中的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若92=(2，4，6，8，20)，则．S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度【2011年全国试题42(15)分】

【正确答案】正确答案：中位数是指长度为L(L≥1)的序列S，在排序后处在第[L／2]个位置的数。一般的叙述是：不用全部排序，找出第j(1≤j≤L)位置的数，即若排序，则在排序后该数的序号为j。如果L为奇数，中位数就1个，否则，中位数有两个。本题简化了，给了两个升序序列，采用计数方法最简单。因为两个有序序列长度为n，若其中位数相等A[n／2]=B[n／2])，则该中位数就是两序列合并后的中位数；否则，对两序列从最小数开始，比较并将小者计数，当数到n时，该数就是两序列合并后的中位数。

【答案解析】