们所有元素的升序序列的中位数

们所有元素的升序序列的中位数。例如，若S2=（246820），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

想必大家想到是O(n)的算法复杂度和O(1)的空间复杂度，那恭喜你了。错了。

算法的基本设计思想如下。 分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下：

1）若a=b，则a或b即为所求中位数，算法结束。

2）若ab，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等；

在保留的两个升序序列中，重复过程1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。