王道课后习题2.2.11:找出等长升序序列A和B的中位数

题目描述：

一个长度为L（L≥1）的升序序列S，处在第 ëL/2ù 个位置的数称为S的中位数。例如，若序列S1=（11，13，15，17，19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2，4，6，8，20），则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

算法思想：

第一种方法是先排好序再求中位数。第二种方法比较复杂。

第一种方法核心代码：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10


int* merge_S1_S2(int S1[],int S2[],int n)//等长序列
{
    int *S=(int *)malloc(sizeof(int)*MaxSize);//注意这里不同于分配单链表的结点，只分配一个sizeof(LNode)就行了。这里是数组，要分配够一片空间。
    int i,j,k;
    i=j=k=0;
    while(i<n&&j<n)
    {
        if(S1[i]<S2[j])
        {
            S[k++]=S1[i++];//总是忘记i++和j++
        }
        else
     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17