1. 实践题目
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列
的中位数指A_(N−1)/2的值,即第⌊(N+1)/2⌋个数（A_0为第1个数）。
输入格式:
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
5
1 3 5 7 9
2 3 4 5 6
输出样例1:
4
输入样例2:
6
-100 -10 1 1 1 1
-50 0 2 3 4 5
输出样例2:
1
2. 题目描述
给出两段非降序数字序列，用算法找出两段数字合并后的中位数，要求时间复杂度为O（logn）
3. 算法描述
一开始想的是老师上课讲的归并排序，将两段数列合并后直接去中间值，但后来老师说，排序最快的时间复杂度是O（nlogn），超过了题目要求的O（logn）
第二个想的方法是做一个永真循环将a数组和b数组的每个数对比一次，但这样的时间复杂度是O（n），也超过了题目要求的O（logn）。
于是小白的我不会了，去向班上的高手请教。
高手说了噼里啪啦一大堆，我听的似懂非懂，只好自己慢慢对着敲了一遍。
大致的意思是，通过一些规律总结，从而借助二分递归的方法，对两段数字分别求中位数。
1) 如果两段序列的中位数相等，那么合并后的中位数即为该数。
if (a[mid1] == b[mid2])
return a[mid1];
2) 如果当第一段的中位数小于第二段的时候，那么两端合中位数一定在第一段中位数后面或第二段中位数前面，这时只取这两部分，再继续进行二分比较
if (a[mid1] < b[mid2]) {
if ((l1 + r1) % 2 == 0) {
l1 = mid1;
r2 = mid2;
}
else {
l1 = mid1 + 1;
r2 = mid2 ;
}
｝
3) 如果当第一段的中位数大于第二段的时候，那么两段合中位数一定在第一段中位数前或第二段中位数后，这时只取这两部分，再继续进行二分比较
{
if ((l1 + r1) % 2 == 0) {
r1 = mid1;
l2 = mid2;
}
else {
r1 = mid1;
l2 = mid2 +1;
}
}
4. 算法时间及空间复杂度分析
l 二分法，递归，时间复杂度为O（logn）。
l 没用用其他的辅助空间，空间复杂度为O（1）。
5. 心得体会
首先，递归是算法之本，但递归的种类又有很多，需要比较深入地去学习。
比如本次的实践题目第三题，用一般的归并，遍历就很难得到想要的结果，而班上同学想出来的二分法递归就很好地契合了O（logn）时间复杂度的要求
其次，作为小白的我对于算法了解的不多，所以我知道，需要多向厉害的同学请教，比如这次的题目，在自己想不出来的情况下，勇敢地向同学求助，集思广益，学习后，自己动手操作几次，也能学到不少东西。