有序数组求中位数问题

有序数组求中位数问题

1、有两个已排好序的数组A和B，长度均为n，找出这两个数组合并后的中间元素，要求时间代价为O(logn)。
2、假设两个有序数组长度不等，同样的求出中位数。
一：解析： 这个题目看起来非常简单。第一题的话： 假设数组长度为n, 那么我就把数组1和数组2直接合并，然后再直接找到中间元素。对于这样的方案，第一题和第二题就没有什么区别了。这样的话时间复杂度就是O(n)。通常在这样的情况下，那些要求比较高的面试官就会循循善诱道：“你还有更好的办法吗？” 如果比线性更高效，直接能想到的就是对数了O(log(n))，这个时间复杂度在这里可能吗？ 当然还是可能的。
算法导论上面的分析是这样的：
Say the two arrays are sorted and increasing, namely A and B.
It is easy to find the median of each array in O(1) time.
Assume the median of array A is m and the median of array B is n. Then，
1、If m==n，then clearly the median after merging is also m，the algorithm holds.
2、If m<=n，then reserve the half of sequence A in which all numbers are greater than m，also reserve the half of sequence B in which all numbers are smaller than n.
Run the algorithm on the two new arrays。
3、If m>n，then reserve the half of sequence A in which all numbers are smaller than m，also reserve the half of sequence B in which all numbers are larger than n.
Run the algorithm on the two new arrays。
Time complexity: O(logn)
下面，我们来画个图，分析一下这个思路：

我们先来分析看看： 想到对数的效率，首先想到的就是二分查找，对于这个题目二分查找的意义在哪里呢？
我们找到了A[n/2] 和 B[n/2]来比较，
1、如果他们相等，那样的话，我们的搜索结束了，因为答案已经找到了A[n/2]就肯定是排序后的中位数了。
2、如果我们发现B[n/2] > A[n/2]，说明什么，这个数字应该在 A[n/2]->A[n]这个序列里面， 或者在 B[1]-B[n/4]这里面。 或者，这里的或者是很重要的， 我们可以说，我们已经成功的把问题变成了在排序完成的数组A[n/2]-A[n]和B[0]-B[n/2]里面找到合并以后的中位数， 显然递归是个不错的选择了。
3、如果B[n/2] < A[n/2]呢？显然就是在A[0]-A[n/2]和B[n/2]-B[n]里面寻找了。
在继续想， 这个递归什么时候收敛呢？当然一个case就是相等的值出现， 如果不出现等到这个n==1的时候也就结束了。
照着这样的思路， 我们比较容易写出如下的代码， 当然边界的值需要自己思量一下（递归代码如下）：

1. // 两个长度相等的有序数组寻找中位数  
2. int Find_Media_Equal_Length(int a[] , int b[] , int length) 
3. { 
4.     if(length == 1) 
5.     { 
6.         return a[0] > b[0] ? b[0] : a[0]; 
7.     } 
8.     int mid = (length-1)/2;   //奇数就取中间的，偶数则去坐标小的  
9.     if(a[mid] == b[mid]) 
10.         return a[mid]; 
11.     else if(a[mid] < b[mid]) 
12.     { 
13.         return Find_Media_Equal_Length(&a[length-mid-1] , &b[0] , mid+1);    //偶数则取剩下的length/2，奇数则取剩下的length/2+1  
14.         //return Find_Media_Equal_Length(a+length-mid-1 , b , mid+1);  
15.     } 
16.     else 
17.     { 
18.         return Find_Media_Equal_Length(&a[0] , &b[length-mid-1] , mid+1); 
19.         //return Find_Media_Equal_Length(a , b+length-mid-1 , mid+1);  
20.     } 
21. } 

 非递归代码如下：

1. // 非递归代码  
2. int Find_Media_Equal_Length(int a[] , int b[] , int length) 
3. { 
4.     int mid; 
5.     while(1) 
6.     { 
7.         if(length == 1) 
8.         { 
9.             return a[0] > b[0] ? b[0] : a[0]; 
10.         } 
11.         mid = (length-1)/2; 
12.         if(a[mid] == b[mid]) 
13.             return a[mid]; 
14.         else if(a[mid] < b[mid]) 
15.             a = a + length - mid - 1;    // a数组的后半部分  
16.         else 
17.             b = b + length - mid - 1;    // b数组的后半部分  
18.         length = mid + 1; 
19.     } 
20. }