给定两个长度相同，分别有序的数组A和B，求两个数组中所有数的中位数

给定两个数组A和B，数组的长度相同都为n，两个数组都分别有序，要求出两个数组中所有数的中位数。

分析：两个数组中总共有2n个数，有两个中位数，这里取较小的那一个。要找出2n个数的中位数，其实就是找出其中第n大的数，用两个下标p,q分别指向A，B两个数组中的第一个元素，如果A中元素较小就移动p,如果B中元素较小就移动q，并计录移动的次数，直到找到第n大的元素为止，总共的移动次数n-1,时间复杂度为O(n)

上述方法的时间复杂度已经比较好了，但是每次只移动一位，没有很好的利用两个数组分别有序的条件，下面提供一个O(logn)的方法。具体步骤:

每次取A数组和B数组的中间元素p和q，比较两个数的大小，如果p等于q，则p和q就是所有数字的中位数; 如果p大于q，则中位数只可能存在A数组的左半部分和B数组的右半部分; 如果p小于q，则中位数只可能存在于A数组的右半部分和B数组的左半部分,这样规模变为原来的一半。

同时有结论，A数组和B数组的子数组中求出的中位数为所有数字的中位数

证明:

假设A和B数组的长度为奇数2k+1, 取A数组的中间元素A[k],取B数组的中间元素B[k], 如果A[k]等于B[k]，则A[k]必为第2k+1大的数，是所有数字的中位数。如果A[k]大于B[k]，则A[k]至少也是第2k+2大的数，B[k]至多为第2k+1大的数，中位数介于B[k]和A[k]之间，因此不可能存在于A数组的右半部分和B数组的左半部分，有效数组的长度为k+1，原来的数字总共有4k+2个，现在变为2k+2个，可以轻易证明这2k+2个数中的中位数就是原来的4k+2个数的中位数，问题规模为原来的一半，当A[k]小于B[k] 的时候情况相似。

假设A和B数组的长度为偶数2k，每次取A数组中靠后的那个中间元素A[k], 取B数组靠前的那个中间元素B[k-1], 如果A[k]等于B[k-1]，则A[k]必为第2k大的元素，是所有数字的中位数。如果A[k]大于B[k]，则A[k]至少也是第2k+1大的数，B[k-1]至多是第2k大的数，中位数介于B[k-1]和A[k]之间，因此只可能出现在A数组的左半部分和B数组的右半部分，数组的长度为看k+1,原来的数字总共有4k个，现在变为2k+2个，可以证明这2k+2个数中的中位数就是原来4k个数的中位数，问题规模为原来的一半,当A[k]小于B[k-1]时情况类似。

　　每次求中位数的时候首先判断数组的长度，然后按照以上的两种规则缩小问题规模，每次都变为原来的一半，因此时间复杂度为O(logn).

　　注意当数组的长度变为2的时候，如果A中为67和72， B中为71和72，就会陷入死循环，需要另作判断

 1 #include <iostream>
 2 #include <assert.h>
 3 using namespace std;
 4 
 5 int MidNum(int *A,int l1,int r1,int *B,int l2,int r2)
 6 {
 7     int mid1,mid2;
 8     assert(A != NULL && B!=NULL && l1<=r1 && l2<=r2 && r1-l1 == r2-l2);
 9     //当两个数组都只剩下一个元素的时候取比较小的数作为中位数
10     if(l1==r1 && l2==r2)
11         return A[l1]<B[l2]?A[l1]:B[l2];
12     //当两个数组中都只剩下两个元素的时候，会出错，例如A中剩下63,72.B中剩
13     //下71,72时
14     if(r1-l1==1)
15     {
16         if(A[l1]<B[l2])
17             return B[l2]<A[r1]?B[l2]:A[r1];
18         else
19             return A[l1]<B[r2]?A[l1]:B[r2];
20     }
21     //当数组的长度为偶数的时候，A数组中取靠后的那个中位数，B数组中取靠
22     //前的那个中位数
23     if((r1-l1+1)%2==0)
24     {
25         mid1=(r1+l1)/2+1;
26         mid2=(r2+l2)/2;
27     }
28     else
29     {
30         mid1=(r1+l1)/2;
31         mid2=(r2+l2)/2;
32     }
33     if(A[mid1]==B[mid2])
34         return A[mid1];
35     else if(A[mid1]>B[mid2])
36         return MidNum(A,l1,mid1,B,mid2,r2);
37     else
38         return MidNum(A,mid1,r1,B,l2,mid2);
39 }
40 
41 int main()
42 {
43     int A[6]={1,3,5,6,8};
44     int B[6]={2,4,6,9,11};
45 
46     int m2=MidNum(A,0,4,B,0,4);
47     cout<<m2<<endl;
48 
49     int A2[10]={17,18,28,37,42,54,63,72,89,96};
50     int B2[10]={3,51,71,72,91,111,121,131,141,1000};
51 
52     int m=MidNum(A2,0,9,B2,0,9);
53     cout<<m<<endl;
54 
55     return 0;
56 }