题目来源：《算法设计与分析》第二版

一.问题：求两个等长升序序列的中位数。

这个题目在前面发表的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）（因为没有开辟新的数组空间）