题目如下：
一个长度为L(L>=1)的升序序列S，处在第L/2(向下取整)个位置的数称为S的中位数。
如序列s1={ 11，13，15，17，19} 中位数为15。而两个升序序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2={2,4,6,8,20},则s1和s2的中位数是11。
? ? ? ?现有两个等长的升序序列A和B，设计一个在时间和空间两方面尽可能高效的算法，找出序列A和B的中位数。
? ? ? ? 当我看到题目，第一个思路就是用线性表的合并算法先把两个有序序列合并为一个，然后求其中位数，这个方法思路很容易就可以想到，实现算法只需要对线性表合并算法稍微做改进，因为题目是要求找到L/2位置的元素，想到顺序表具有随机存取的特性，自然使用顺序表，然后在合并算法中当合并到第(A_length+B_length)/2个元素时，返回它的元素值，此题目就可以完成了。
? ? ? ? 但是合并算法的时间复杂度为O(n); 而且要预先分配A和B的空间大小之和的空间，空间复杂度为O(A_length+B_length)。
然而，还有一种在时间和空间上更加高效的算法，接下来我来介绍这个算法。
? ? ? ? 从题目出发，考虑两个升序序列中位数的位置会出现的范围，比如题目中的这两序列
? ?s1={ 11，13，15，17，19}? ? ? ??S2={ 2，4，6，8，20}
? ?很容易得到s1的中位数为 15，s2 的中位数为 6，? ? s1和s2的中位数是11。可以发现11在6和15之间，即：s1和s2的中位数一定出现在s1的中位数和s2的中位数之间。我们将用这个思路对s1和s2划分。
? ? ? ? ?s1和s2的中位数，一定出现在s1的中位数15之前的部分（11，13，15），不会出现在15之后的部分（17,19）。同样，s1和s2的中位数，一定出现在6之后的部分（6，8，20），不会出现在6之前的部分（2,4）。
? ? ? s1变为{11，13，15}，s2变为{6，8，20}；
? ? ? s1的中位数为13，s2的中位数为8
? ? ? 同样的道理我们应该舍弃s1中13以后的部分（15），s2中8以前的部分（6）。
? ? ?s1变为{11，13}，s2变为{8，20}；
? ? ?s1的中位数为11，s2的中位数为8。
? ? ?这里会出现个问题，如果按照刚才的做法继续会发现
? ? s1变为（11），s2变为（8，20），这里的8到底应不应该出现呢？
? ? ?s1与s2原本都有偶数个元素 因为s1的中位数11>s2的中位数8，所以合并s1与s2，8只能在11的前面，而11所在的位置不会大于（A_length+B_length）/2,8还在11之前，所以8一定不会是s1和s2的中位数。
? ? ?所以 s1应该变为{11}，s2应该变为{20}
? ? ? 比较 11<20 所以11就是中位数。
算法描述：
?1 求A的中位数m1,B的中位数m2.
?2 如果m1=m2，则中位数为m1
?3 如果m1<m2,舍弃m1前一半，舍弃m2后一半。
?4 如果m1>m2,舍弃m1后一半，舍弃m2前一半。
?5 舍弃后的序列中不断执行2，3，最后A,B各剩下一个元素，取其中最小的元素就是中位数。
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int FindMidNum(int *a,int *b,int n){
int s1=0,d1=n-1,s2=0,d2=n-1;
int m1=0,m2=0;
while(s1!=d1||s2!=d2) {
m1 = (s1+d1)/2;
m2 = (s2+d2)/2;
if(a[m1]==b[m2]) return a[m1];
if(a[m1]<b[m2]) {
if((s1+d1)%2==0) {
s1 = m1;
d2 = m2;
}
else{
s1 = m1+1;
d2 = m2;
}
}
else {
if((s1+d1)%2==0) {
d1 = m1;
s2 = m2;
// printf("s2 = %d\n",s2);
}
else{
d1 = m1;
s2 = m2+1;
// printf("d1 = %d\n",d1);
}
}
}
return a[s1]<b[s2]?a[s1]:b[s2];
}
int main(){
int a[] = {11,13,15,17,19};
int b[] = {2,4,6,8,20};
printf("中位数 = %d",FindMidNum(a,b,5));
}
此算法时间复杂度为O(log2n)，空间复杂度为O(1).
测试结果：
?
? ??
? ? ? ?