分治与递归-XY中位数问题

给定两个具有n个元素的数组X和Y，X和Y已排好序，X+Y的中位数，共2n个元素，期望lnN级别的解决

易知，中位数两边的数都是n个，那么假设该中位数是X[mid]，则其左边的数构成为：X[0:mid-1]+Y[0:n-1-mid]，其右边的数构成为：X[mid:n-1]+Y[mid:n-1]，故可知中位数X[mid]满足条件如下：

Y[n-2-mid] <= X[mid] <= Y[n-1-mid]

代码实现：

#include <stdio.h>
bool GetValue(int *X,int *Y,int n,int& value)
{
 int low = 0 , high = n - 1 , mid;
 while(low <= high)
 {
  mid = (low + high) / 2;
  if(mid == n - 1)
  {
   if(X[mid] <= Y[0])
   {
    value = X[mid];
    return true;
   }
   else return false;
  }
  else if(mid==0)
  {
      if(X[mid]>=Y[0])
      {
          value=X[mid];
          return true;
      }
  }
  else
  {
   if(X[mid] <= Y[n - mid - 1] && X[mid] >= Y[n - mid - 2])
   {
    value = X[mid];
    return true;
   }
   else if(X[mid]<=Y[n-mid-2])
                low++;
            else
                high--;
  }
 }
 return false;
}
int GetMiddle(int *X,int *Y,int n)
{
 int value;
 // 这个中位数不是在 X 中就是在 Y 中
 if(GetValue(X,Y,n,value) == false){
  GetValue(Y,X,n,value);
 }
 return value;
}
int main()
{
    int n,i,m;
    printf("please putin the length:\n");
    scanf("%d",&n);
    int x[n];
    int y[n];
    printf("please putin the first num[]:\n");
    for(i=0;i<n;++i)
        scanf("%d",&x[i]);
    printf("please putin the second num[]:\n");
    for(i=0;i<n;++i)
        scanf("%d",&y[i]);
    m=GetMiddle(x,y,n);
    printf("the middle is %d\n",m);
    return 0;
}