求两个等长有序序列的中位数

#include<iostream>

using namespace std;

void ZhWei(int m[],int n[],int k)

{

int s1=0,e1=k-1,s2=0,e2=k-1;//初始化初始化两个序列的上下限；

int mid1;

int mid2;

while(s1<e1&&s2<e2)

{

 mid1=(s1+e1)/2;//序列m的中位数下标

 mid2=(s2+e2)/2;//中位数n的中位数下标

 if(mid1==mid2)

 {

     cout<<m[mid1];

     return;

 }

 else if(m[mid1]<n[mid2])

 {

  s1=mid1+1;

  if((s2+e2)%2==0)

  {

   e2=mid2-1;

  }

   else e2=mid2;

 }

  else

  {

   s2=mid2+1;

   if((s1+e1)%2==0)

   {

    e1=mid1-1;

   }

    else

    {

     e1=mid1;

    }

  }

}

  if(m[s1]<n[s2])//较小者即为所求

  cout<<m[s1];

  else

  cout<<n[s2];

   return;

 }

 void main()

 {

  int n[100];

  int m[100];

  int k;

  cout<<"数组元素的个数"<<endl;

  cin>>k;

  for(int i=0;i<k;i++)

  {

   cin>>n[i];

  }

  for(int j=0;j<k;j++)

  {

 cin>>m[j];

  }

     ZhWei(m,n, k);

 }

由于每次求两个有序序列的中位数后，得到的两个子序列的长都是上溢序列的一半，因此循环共执行log2n次，时间复杂度为O(log2n),算法除简单变量外没有额外开辟存储空间 ，因此空间复杂度为O(1)