有序數組求中位數問題

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. }