2019-05-11等长度的升序序列A,B 找出两个序列A和B的

参考：https://www.tomorrow.wiki/archives/1157

image.png

中位数的概念：

对于数集 就是数集排序后中间位置的那个数，集合有偶数个数 中位数就是将 中间两个数的平均数

此题还需要注意的是 ：两个序列的长度是一样的，若两个序列长度是不一样的（需要思考）

image.png

解题的关键：
1、找出两个序列的中位数 比较 舍去比小的小的部分，比大的大的部分（舍去的长度是相同的）
2、如何判断 减去的长度是 ：需要舍弃的两个数的更小的值

image.png image.png

int m_search(int A[], int B[], int n )
{
    /*分别表示序列 A B 的首位数 末尾数 中位数*/
    int s1=0, d1=n-1, m1;     
    int s2=0, d2=n-1, m2;

    while(s1!=d1 || s2!=d2)
    {
        m1 = (s1+d1)/2;
        m2 = (s2+d2)/2;

        if(A[m1]==B[m2])/*满足条件 1*/
            return A[m1];

        if(A[m1]<B[m2])/*满足条件 2*/
        {
            if( (s1+d1)%2==0 )/*元素个数为奇数*/
            {
                s1=m1;/*舍弃 A 中间点以前的部分并保留中间点*/
                d2=m2;/*舍弃 B 中间点以后的部分并保留中间点*/
            }
            else/*元素个数为偶数*/
            {
                s1=m1+1;/*舍弃 A 中间点以前部分以及中间点*/
                d2=m2;/*舍弃 B 中间点以后部分并保留中间点*/
            }
        }
        else/*满足条件 3*/
        {
            if( (s2+d2)%2==0 )
            {
                d1=m1;
                s2=m2;
            }
            else
            {
                d1=m1;
                s2=m2+1;
            }
        }
    }

    return A[s1]<B[s2]? A[s1]:B[s2];
}