一个长度为L（L>=1）的升序序列S，处在L/2(向上取整）个位置的数称为S的中位数。例如，若序列S1={11,13,15,17,19}，则S的中位数是15，两个序列的中位数是含他们所有元素的升序序列的中位数。例如，若S2={2,4,6,8,20}，则S1和S2的中位数是11。现在有两个等长升序序列A个B，试找出两个序列A和B的中位数。
方法一：
思想：先进行合并，然后找出合并后这个表的中位数。
代码：
bool merge(SqList &A，SqList &B,SqList &C) {
if(A.length + B.length > MaxSize){
return false;
}
int indexA=0,indexB=0;indexC=0;
while(index < A.length && indexB < B.length){//归并两个表
if(A.data[indexA] <= B.data[indexB]){
C.data[indexC++]=A.data[indexA++];
}else{
C.data[indexC++]=B.data[indexB++];
}
}
while(index < A.length){//A表有剩余
C.data[indexC++]=A.data[indexA++];
}
while(indexB < B.length){//B表有剩余
C.data[indexC++]=B.data[indexB++];
}
//表C的长度
C.length=indexC;
return true;
}
bool getMid(SqList &A,SqList &B,ElemType &x){
if(A.length != B.length || A.length <=0){//合法性判断
return false;
}
//进行归并排序
SqList C;
merge(A,B,C);
//返回中位数
x=C.data[C.length/2-1];
return true;
}时间复杂度O(n)；空间复杂度O（1）
方法二：
对于本题来说，合并后的序列一定是偶数个。中位数左边的数均比它小，右边的数均比它大，在中位数的左边和右边同时删除或增加等长的元素，中位数不会改变。
思想：求两个升序序列A和B的作为数，将A的中位数设为midA，B的中位数设为midB。
当midA=midB时，midA或midB为中位数，算法结束。
当midA<midB时，舍弃A中较小的一半，舍弃B中交大的一半，舍弃的元素个数相同。
当midA>midB时，舍弃B中较小的一半，舍弃A中交大的一半，舍弃的元素个数相同。
重复上述过程，知道两个序列中均只有一个元素时，较小的为两个序列的中位数。
代码：
bool getMid(SqList &A,SqList &B,ElemType &x){
if(A.length != B.length || A.length <=0){//合法性判断
return false;
}
int i,di,midA,j,dj,midB;
i=0;//表示表A开始时的下标
di=A.length-1;//表示表A最后一个元素的下标
j=0;//表示表B开始时的下标
dj=B.length-1;//表示表B最后一个元素的下标
while(i != di || j != dj){//两个表中的元素都超过一个元素时，大于等于2，均只有一个元素时，选择最小的即可
//中位数下标
midA=(i+di)/2;
midB=(j+dj)/2;
//表A和标B的中位数相等时，找到两个表的中位数
if(A.data[midA]==B.data[midB]){
x=A.data[midA];
return true;
}
else if(A.data[midA]<B.data[midB]){//表A的中位数小于表B的中位数时，舍弃表A较小的一半，舍弃表B较大的一半
dj=midB;
i=(di+midA)%2 ==0 ? midA:(midA+1);
} else{//表A的中位数大于表B的中位数时，舍弃表A较大的一半，舍弃表B较小的一半
di=midA;
j=(di+midB)%2 == 0 ? midB:(midB+1);
}
}
x=A.data[i] < B.data[j] ? A.data[i]:B.data[j];//两个表中只剩下一个元素时，中位数为最小的一个。
}时间复杂度O（logn）空间复杂度O(1)