用O(lgn)时间求出两个已排序数组的中位数


相关问题：

设 x[1..n]和Y[1..n]为两个数组，每个都包含n个已排序的数。给出一个求数组X和Y中所有2n个元素的中位数的O(lgn)时间的算法。

思考过程：

        开始我想把两个数组X与Y放入到一个数组Z中，对Z进行排序，这样Z的中位数易求。但是有2点原因使得这种做法不可行，1.是将2数组放入到1个数组中的过程会产生O(n)的时间，所以不满足题意。2如果对新数组Z排序，那么最少需要线性O(n)时间进行排序，也不满足O(lgn)这个时间的需求。然后我又试图用最坏时间线性选择子程序，但是马上想到，这样就是O(n)，不是O(lgn)的时间了，所以用不上书中9.3节的内容。

        后来我想到如果要想达到O(lgn)这个数量级的查找，那么可以选择二分法进行查找，首先判断数组X（Y）是否所有数都小于数组Y（X），如果假设成立，那么直接返回数组X最后一个数即可。如果集合X与Y之中的数存在集合X的某元素＜集合Y的某元素，同时集合X的某元素＞集合Y的某元素，那么进入递归。具体递归过程请见代码注释。（PS：其实我认为这个问题就是考察对二分法的灵活运用。）

具体步骤：

   开始随机化数组，然后对数组进行排序。因为原题的意思是要想进行O(lgn)时间的选择，那么前提是两数组已排序，所以不能将排序过程算在总的选择时间里面。当然你也可以选择自己设置数组元素值，使其初始化时便已有序。

      Two_groups_array_Median函数具体步骤是：

step 1：判断数组X（Y）所有数是否均小于数组Y（X）所有数。如果小于，则直接返回中位数。程序立即结束。

step 2：判断数组X与Y，begin项≥end项？如果成立，则进入最后的微调与返回中位数阶段。

step 3：如果step 1，2都不成立，那么进入二分法的递归过程。具体过程见代码注释。

 

#include <iostream>
#include <time.h>
using namespace std;
const n=25;
void INSERTION_SORT(int A[],int r)//利用任意一个排序算法设置数组为题目条件“有序”。
{
    int key;
    for (int j=1;j<=r;j++)
    {
        key=A[j-1];
        int i=j-1;
        while (i>0&&A[i-1]>key)//a)插入排序时间复杂度O(n^2)对于长度为k的子列表都有O(k^2),则n/k个为(k^2)*n/k=O(nk)
        {
            A[i]=A[i-1];
            i=i-1;
        }
        A[i]=key;
    }
}
void Initialization(int A[],int r,int a,int b)//初始化数组
{
    srand( (unsigned)time( NULL ) );
    for (int i=0;i<n;i++)
    {
        A[i]=rand()%(a-b+1)+b;
    }
}
void Print(int A[],int r)
{
    for (int i=0;i<r;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
}
int Two_groups_array_Median(int A[],int B[],int beginA,int endA,int beginB,int endB)
{
   int p=(beginA+endA)/2;int r=(beginB+endB)/2;
   int t=p+r+2,flag=0;//经过大量的实验证明（我试图用数学归纳法证明，惭愧的是我没有完整证明出来，如果有大牛觉的我的这个结论是错误的，那么可以举反例证明我的错误以待我去改正，小弟在此先感谢纠正我错误给我留言的人）：t≈n 最多相差常数个误差。误差产生的原因是p和r定义时除以2后，全部向下取整了，而精确的中位数是需要有时向上取整的。
   //t表示当前中位数p和r前面有多少个元素，由于数组下标是从0开始的，所以需要+上A[0]和B[0]。
   if (A[n-1]<B[0])//如果集合A与B之中的某一集合所有的数均小于另外一集合所有数，则直接返回较小数组的最后一位即为中位数
   {
        return A[n-1];
   }
   else if (A[0]>B[n-1])
   {
        return B[n-1];
   }
   if (beginA>=endA||beginB>=endB)//如果A与B哪个先递归到begin项≥end项，那么就进行下面的判断。
   {
       if (n-t>0)
       {
           for (int i=1;i<=n-t;i++)//对于上面注释所说的误差所差常数的具体数值，根据这个常数数值再求精确的中位数，否则如果没有这个循环，那么所求中位数与真实中位数要相差常数个位置
           {
               ++p;++r;
               if (A[p]<B[r])
               {
                   --r;
                   flag=1;
               }
               else 
               {
                   --p;
                   flag=0;
               }
           }
           if (flag)//这个if-else语句是要返回A与B中较小的那个数，较小的数就是中位数。
           {
               return A[p];
           }
           else
           {
               return B[r];
           }
       }
       else//如果n=t，无需进行微调，由于p+r+2正好等于这2n个数的中间值下标n，那么就返回较大值，较大值正好是第n个数。
       {
           if (A[p]<B[r])
           {
               return B[r];
           }
           else
           {
               return A[p];
           }
       }
   }
   if (A[p]>B[r])//如果数组A的中位数大于数组B的中位数，那么两数组的中位数必在数组A当前中位数的左边，数组B当前中位数的右边
   {
      return Two_groups_array_Median(A,B,beginA,p,r,endB);//对数组A的左半部分数组B的右半部分进行递归。
   }
   else //小于情况类似，这里不做累述。
   {
      return Two_groups_array_Median(A,B,p,endA,beginB,r);
   }
}
void main()
{
    int A[n]={0},B[n]={0};
    cout<<"随机数组A初始化。。。"<<endl;
    Initialization(A,n,10000,9);
    INSERTION_SORT(A,n);//利用插入排序设置数组使其变为题目所说的“已排序”的数组。
    Print(A,n);
    cout<<"随机数组B初始化。。。"<<endl;
    Initialization(B,n,15000,1000);
    INSERTION_SORT(B,n);
    Print(B,n);
    cout<<"两数组中位数="<<Two_groups_array_Median(A,B,0,n-1,0,n-1)<<endl;
}


相关内容