思想:分别求A,B的中位数,若a=吧,则a或b为所求中位数,否则,舍弃a,b中最小者所在序列之较小一半,同时舍弃较大者所在序列较大一半,要求两次舍弃元素个数相同,重复上述过程,直到两个序列中只含一个元素为止,则较小者为所求中位数。

代码:

int search(int a[],int b[],int n)
{
    int s1,e1,mid1,s2,e2,mid2;
    s1=0;e1=n-1;s2=1;e2=n-1;
    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])
        {
            if((s1+e1)%2==0)//若元素个数为奇数个
            {
                s1=mid1;//舍弃a中间点以前部分并保留中间点
                e2=mid2;//舍弃b中间点以后部分并保留中间点
            }
            else
            {
                s1=mid1+1;//舍弃a中间点以前部分及中间点
                e2=mid2;//舍弃b中间点以前部分并保留中间点
            }

        }
        else
        {
             if((s1+e1)%2==0)//若元素个数为奇数个
            {
                e1=mid1;//舍弃a中间点以后部分并保留中间点
                s2=mid2;//舍弃b中间点以前部分并保留中间点
            }
            else
            {
                e1=mid1+1;//舍弃a中间点以前部分并保留中间点
                s2=mid2;//舍弃b中间点以前部分和中间点
            }
        }

    }
    return(a[s1]<b[s2]?a[s1]:b[s2]);
}
02-11 12:59