有序數組中找中位數

題目：兩個有序數組a和b，大小都是n，尋找這兩個數組合并後的中位數。時間複雜度為o(logn)。

中位數：如果數組的個數是奇數，那麼中位數的值就是有序時處于中間的數；如果數組個數是偶數的，那麼就是有序時中間兩個數的平均值。

方法一：合并時計數

使用merge sort時的merge操作，比較兩個數組時候計數，當計數達到n時，就可以得到中位數，在歸并的數組中，中位數為下标n-1和n的兩個數的平均值。

時間複雜度o(n)。

方法二：比較兩個數組的中位數

ar1[]和ar2[]為輸入的數組

算法過程：

1.得到數組ar1和ar2的中位數m1和m2

2.如果m1==m2，則完成，傳回m1或者m2

3.如果m1>m2，則中位數在下面兩個子數組中

a) from first element of ar1 to m1 (ar1[0...|_n/2_|])

b) from m2 to last element of ar2 (ar2[|_n/2_|...n-1])

4.如果m1<m2，則中位數在下面兩個子數組中

a) from m1 to last element of ar1 (ar1[|_n/2_|...n-1])

b) from first element of ar2 to m2 (ar2[0...|_n/2_|])

5.重複上面的過程，直到兩個子數組的大小都變成2

6.如果兩個子數組的大小都變成2，使用下面的式子得到中位數：median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

時間複雜度：o(logn)。

方法三：通過二分查找法來找中位數

基本思想是：假設ar1[i]是合并後的中位數，那麼ar1[i]大于ar1[]中前i-1個數，且大于ar2[]中前j=n-i-1個數。通過ar1[i]和ar2[j]、ar2[j+1]兩個數的比較，在ar1[i]的左邊或者ar1[i]右邊繼續進行二分查找。對于兩個數組 ar1[] 和ar2[], 先在 ar1[] 中做二分查找。如果在ar1[]中沒找到中位數, 繼續在ar2[]中查找。

算法流程：

1) 得到數組ar1[]最中間的數，假設下标為i.

2) 計算對應在數組ar2[]的下标j，j = n-i-1 

3) 如果 ar1[i] >= ar2[j] and ar1[i] <= ar2[j+1]，那麼 ar1[i] 和 ar2[j] 就是兩個中間元素，傳回ar2[j] 和 ar1[i] 的平均值

4) 如果 ar1[i] 大于 ar2[j] 和 ar2[j+1] 那麼在ar1[i]的左部分做二分查找(i.e., arr[left ... i-1])

5) 如果 ar1[i] 小于 ar2[j] 和 ar2[j+1] 那麼在ar1[i]的右部分做二分查找(i.e., arr[i+1....right])

6) 如果到達數組ar1[]的邊界(left or right)，則在數組ar2[]中做二分查找

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。

http://www.cnblogs.com/luxiaoxun/archive/2012/09/13/2684054.html