有序數組求中位數問題

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