medi.cpp

设X[0:n-1]和Y[0:n-1] 为2 个数组,每个数组中含有n 个已排好序的数。试设计一个O(log n) 时间的算法,找出X 和Y 的2n 个数的中位数。

#include <stdio.h>
#include <malloc.h>
void med(int *X,int i1,int j1,int *Y,int i2,int j2,int n)
{
    int m1,m2;
    n=(j1-i1+1)+(j2-i2+1);//统计两个数组元素个数

    if(n>3)
    {
        if((j1-i1)>(j2-i2))
    	{
            j2+=(j1-i1)-(j2-i2);
    	}
        else{
            j1+=(j2-i2)-(j1-i1);
    	}
        m1= (i1+j1)/2;
        m2= (i2+j2)/2;
        if(X[i1] >= Y[j2])
    	{
    		
            printf("%d\n",Y[j2]);
    	}
        else if(X[j1] <= Y[i2])
    	{
            printf("%d\n",X[j1]);
    	}
        else{
            if (X[m1] == Y[m2])
    		{
             printf("%d\n",X[m1]);
    		}
            else if(X[m1] < Y[m2])
    		{
        //   printf("<<<<<< %d,%d,%d,%d,%d\n",m1,j1,i2,m2,n);
             med(X,m1,j1,Y,i2,m2,n);
    		}
        	else{
        //   printf(">>>>>> %d,%d,%d,%d,%d\n",i1,m1,m2,j2,n);
             med(X,i1,m1,Y,m2,j2,n);
    		}
    	}
    }
    else{
    //  printf(">>>>>> %d,%d,%d,%d,%d\n",i1,j1,i2,j2,n);
        if(i1==j1)
    	{
            if(X[i1]>Y[j2])
             printf("%d\n",Y[j2]); 
            else if(X[i1]<Y[i2])
             printf("%d\n",Y[i2]);
            else printf("%d\n",X[i1]);  
    	}
        else{
            if(X[i1]>Y[i2])
             printf("%d\n",X[i1]); 
            else if(X[j1]<Y[j2])
             printf("%d\n",X[j1]);
            else printf("%d\n",Y[i2]);  		
    	}
     }
 }
 void main()
 {
    int i,n,*a,*b;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d",&n);
    a=(int *)malloc(n*sizeof(int));
    b=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
        scanf("%d",&b[i]);
    med(a,0,n-1,b,0,n-1,n);
 }