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

      [解析]O(lgn)的时间复杂度就是二分查找的复杂度。首先给出一个观察：如果所有元素的中位数是X，那么从数组中同时删除num个小于X的的元素和num个大于X的元素后，产生的新集合的中位数还是X。考虑如下思路求解：每次比较A，B数组的中项元素A[n/2],B[n/2]，代码实现如下：

 

int FindMiddleElement(int A[],int B[],int n)  {      if (n == 1)      {          return A[0] > B[0] ? B[0] : A[0];      }          if (A[n/2] == B[n/2])      {          return A[n/2];      }          if (A[n/2]>B[n/2])  　　{　　　   // 需要确保A和B中丢掉相同数量的元素                           if (n%2 == 0)    //丢掉B[0...n/2 - 1]和A[n/2...n-1]          {			return FindMiddleElement(A,B + n/2,n/2);		}        else    //丢掉B[0...n/2 - 1]和A[n/2 + 1...n-1]          {		    return FindMiddleElement(A,B + n/2,n/2 + 1);      }      else       {		// 需要确保A和B中丢掉相同数量的元素          if (n%2 == 0)    //丢掉A[0...n/2 - 1]和B[n/2...n-1]  		{            return FindMiddleElement(A + n/2,B,n/2);		}        else    //丢掉A[0...n/2 - 1]和B[n/2 + 1...n-1]   		{            return FindMiddleElement(A + n/2,B,n/2 + 1); 	    }    }  }