求兩個數組的中位數

求兩個數組的中位數

博客分類：
• 算法

算法編程 

1,題目
有兩個數組,均已經按升序排列好,編程序計算這兩個數組的中位數
要求:要求時間複雜度O(lgn)   空間複雜度O(1)
例子:
數組A:{1,4,6,7,9}   B{2,3,5,8}     兩數組合並後{1,2,3,4,5,6,7,8,9}   中位數就是中間的那個數: 5
2,方法:

對兩個數組分別二分找解
對每個元素可以O(1)判斷它在另外一個數組應該所在的位置，從而可以判斷選大了還是小了，繼續二分直到找到解為止

先二分第一個數組找解，可選區域為[0,4]。選中A[2]=6,6前麵有兩個元素，如果將其插入第二個數組，那麽6如果是解，則必須前麵有4-2=2個元素（排第三位）
通過比較前後元素發現6放在B中的第三位明顯大了，需要更小的元素，這樣就將下一次二分的區域減了一半.

在A和B中重複這個過程，直到找到解為止

3，3,擴展

M個長度為N的排序好的數組 求中位數
目前有兩個比較好的算法

算法一
(1)取所有數組的最小值和最大值,求出全體的最大值和最小值min max 然後取m=(min+max)/2
(2)用m在所有數組中搜索 找到比m小的數的個數n1 若n1大於M*N/2 則mid=(min+mid)/2 否則mid=(mid+max)/2
(3)重複上述搜索一共循環log(max-min)次


算法二
(1)取所有數組的中值排序
棄掉這個最大值所在數組的後半部分和最小值所在數組的前半部分 再將這兩個隻剩一半的數組合並 O(N)
(2)從合並後的數組中找出中值插入到之前的中值排序數組裏 o(logN)
(3)重複(1)(2),每次循環可以舍掉一個數組,一共需要循環M次