题目描述：
Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the non-decreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.
Given two increasing sequences of integers, you are asked to find their median.
输入：
Each input file may contain more than one test case.
Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤1000000) is the size of that sequence. Then N integers follow, separated by a space.
It is guaranteed that all the integers are in the range of long int.
输出：
For each test case you should output the median of the two given sequences in a line.
样例输入：
4 11 12 13 14
5 9 10 15 16 17
样例输出：
13
代码：
#include <stdio.h>
#include <stdlib.h>
int * arr1,* arr2,* newArr;
int main(){
int len1,len2;
while(scanf("%d", &len1) != EOF){
arr1 = (int *)malloc(len1*4);
int i;
for(i=0; i<len1; i++)
scanf("%d",&arr1[i]);
scanf("%d", &len2);
arr2 = (int *)malloc(len2*4);
newArr = (int *)malloc( (len1+len2)*4);
for(i=0; i<len2; i++)
scanf("%d",&arr2[i]);
i=0;
int index=0,j=0;
while(i<len1 && j<len2){
if(arr1[i] < arr2[j])
newArr[index++] = arr1[i++];
else
newArr[index++] = arr2[j++];
}
while(i <len1)
newArr[index++] = arr1[i++];
while(j <len2)
newArr[index++] = arr2[j++];
printf("%d\n",newArr[(index-1)/2]);
}
return 0;
}
一只狗的提醒：
这个题目我找了好多博客，上面讲的大都是下面这些
给定两个非递减数组，求出它们的中间元素。
具体来说，就是将它们排成一个非递减序列，然后求出中间位置的元素。
由两个数组序列得到另一个由它们组成的非递减的序列，明显用归并排序，时间复杂度在O(m+n)内完成。
归并排序，用两个指针指向数组开头元素，比较首个元素大小，小的那个元素输出，并且指针往后移一个
再进行比较，循环下去直到某一个序列结束，之后就直接将另一个序列的其余元素输出即可。
这道题，不需要复杂，其实最好的办法，就是二分法查找出中间值即可，但是那个办法留在查找一部分AC
这里我们用两种比较浪费的方式，一种是nlgn的排序办法，但是由于数据规模较小，仍被允许，
第二种是归并排序，仍可接受。
值得注意是，在我们发现WA时，先不要着急，我们多试几组测试用例，自己设计极端情况，
并且仔细读原题，耐心才是解决WA的关键，很多人做题时本机能运行，提交就WA，
这种都是由于有些CASE过不了造成的，一定是程序还有问题。
但是好多代码都不能用，这个是能顺利编译的一个，你也可以参考一下网络资料。