题目来源：《算法设计与分析》第二版
一.问题：求两个等长升序序列的中位数。
这个题目在前面发表的leetcode题目是一样的。
二.分析：
1. 第一种思路
求中位数，中位数是什么？就是有序序列最中间的哪个数字，数学上，奇数个数的中位数就是最中间的数字，偶数个数字是最中间两个数字的平均。
那么大概就有了一个想法，写了下面的草稿（不算伪算法）
1.合并序列（因为是升序序列，合并起来也很简单）
1.1 从A序列和B序列中取数据
1.1.1 若A数据 >= B数据 ，则在新序列中放入A数据
1.1.2 若A数据 >= B数据 ，则在新序列中放入B数据
1.2 若A序列中的数据已经取完，那么在新序列中填入B的剩余数据，否则填入A的剩余数据。
2.如果序列长度是偶数，取中间两个取平均，否则取中间。
合并升序序列，相信大家也都会，也不用研究这个算法到底是怎么个意思，我们直接来看相对优秀的算法。
2.第二种思路
算法跟数学的关系是密不可分的，计算机算法也就是程序实现的数学方法，那么我们可以回想一下，初中学的中位数是怎么求的，就是大家在卷子上做中位数的题是怎么做的。
我看了书上给的解答确实很吃惊，因为他给的方法是跟我小时候数学课堂上求的方法一样。逐渐去掉一个最高的一个最低的，直到最后剩下的一个数，或者两个数，那么最后就知道中位数是怎么求了吧。
那么换作程序应该怎么理解呢？
第一步：分别求两个序列的中位数a,b
第二步：比较a,b大小
如果a == b，那么a就是中位数
如果a < b 则中位数只能在[a,b]区间内，那么就要进行排除最高最低分了，去掉小于a的（A序列排在a前面的数据），大于b的（B序列排在b后面的数据）
同理b < a 则中位数存在[b，a]区间内，那么就要排除最高最低分，去掉小于b的（B序列排在b前面的数据），大于a的（A序列排在a前面的数据）
第三步：当两序列各只剩下一个数字的时候，选小的哪个就是中位数
首先，你看完这段文字可能不太理解。举个例子:
序列A：{11,13,15,17,19}
序列B：{2,4,10,15,20}
第一步：选出两者的中位数a = 15，b = 10
符合a > b 上述第三条，去掉B中小于b，A大于a的
序列A 变成 {11，13，15}，序列B变成{10，15，20},为什么这么操作？
结合我们说的去掉一个最小数一个最大数，我们可以知道在升序序列A，B中，b前面一定小于b，a后面一定大于a，可以直接去掉（去掉了两个最小，两个最大），仔细理解一下，如果是乱序序列就不能这么做了。同时也不要因为我说的去掉最高最低就按照数学思想来较真（2对应20，4对应19……等等）。你可以自己些几个升序序列来验证一下
同时这是减治法的一个应用，把大问题规模，缩小来解题。只关心最终小规模问题的答案，不用返回操作结果。（区分分治法）
代码
/**
* 求两个升序序列的中位数
* by surine 2018年3月28日 20点26分
* */
public class Mid {
public static void main(String[] args) {
int[] a = new int[]{1,4,5,6,8};
int[] b = new int[]{4,5,6,10,13};
int n = a.length;
System.out.println(SearchMid(a,b,n));
}
private static int SearchMid(int[] a, int[] b, int n) {
//声明两个数组的起点下标，终点下标
int s1 = 0,e1 = n - 1,s2 = 0,e2 = n - 1;
//声明中点坐标
int mid1,mid2;
while (s1 < e1 && s2 < e2){
mid1 = (s1 + e1)/2;
mid2 = (s2 + e2)/2;
//第一种情况
if(a[mid1] == b[mid2]){
return a[mid1];
}
//第二种情况
if(a[mid1] < b[mid2]){
//对序列a操作(考虑到序列是奇数个数据还是偶数个数据的情况，这里其实容易理解的
// 画一个奇数序列和偶数序列看看下标情况就知道了。)
if((s1 + e1) % 2 == 0){
s1 = mid1;
}else {
s1 = mid1 + 1;
}
//对序列B操作
e2 = mid2;
}else{ //第三种情况
//对序列b操作(考虑到序列是奇数个数据还是偶数个数据的情况)
if((s2 + e2) % 2 == 0){
s2 = mid2;
}else {
s2 = mid2 + 1;
}
//对序列B操作
e1 = mid1;
}
}
//返回较小值
if(a[s1] < b[s2]){
return a[s1];
}else{
return b[s2];
}
}
}
总结
时间复杂度 O（log2n）（注意不是2n，是log2为底）
空间复杂度O（1）（因为没有开辟新的数组空间）
