牛骨文教育服务平台(让学习变的简单)

问题描述

一个长度为L(L ≥1) 的升序序列S,处在第 ⌜ L/2 ⌝ 个位置的数称为S的中位数。例如,若序列S1=(11,13,15,17,19),则S1的中位数是15;
两个序列的中位数是含它们所有元素所组成的升序序列的中位数。例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。
现在有两个等长升序序列A和B,试设计一个在时间和空间都尽可能高效的算法,找出两个序列A和B的中位数。

算法思想

分别求两个升序序列A,B中位数,设为a和b
1). 若a=b,则a或b即为所求中位数,算法结束;
2). 若a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两次舍弃的长度相等;
3). 若a>b,则设计序列A中较大的一半,同时设计序列B中较小的一半,要求两次舍弃的长度相等;

算法描述

int FindMid(int A[], int B[])
{
    int s1=0,d1=MaxSize-1,m1;
    int s2=0,d2=MaxSize-1,m2;

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

        if(A[m1]<B[m2]){
            if((s1+d1)%2==0){
                s1=m1;
                d2=m2;
            }else{
                s1=m1+1;
                d2=m2;
            }
        }else if(A[m1]>B[2]){
            if((s2+d2)%2==0){
                d1=m1;
                s2=m2;
            }else{
                d1=m1;
                s2=m2+1;
            }
        }else{
            return A[m1];
        }
    }
    return A[s1]<B[s2]?A[s1]:B[s2];
}

具体代码见附件

附件

#include<stdio.h>
#define MaxSize 5

int FindMid(int*, int*);

int main(int argc,char* argv[])
{
    int A[MaxSize]={11,13,15,17,19};
    int B[MaxSize]={2,4,6,8,20};

    int Num;
    Num=FindMid(A,B);
    printf("The mid Num is %d
",Num);
    return 0;
}

int FindMid(int A[], int B[])
{
    int s1=0,d1=MaxSize-1,m1;
    int s2=0,d2=MaxSize-1,m2;

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

        if(A[m1]<B[m2]){
            if((s1+d1)%2==0){
                s1=m1;
                d2=m2;
            }else{
                s1=m1+1;
                d2=m2;
            }
        }else if(A[m1]>B[2]){
            if((s2+d2)%2==0){
                d1=m1;
                s2=m2;
            }else{
                d1=m1;
                s2=m2+1;
            }
        }else{
            return A[m1];
        }
    }
    return A[s1]<B[s2]?A[s1]:B[s2];
}