[理工] [algo/演算法] 兩個已排序的陣列找中間值

[mozzan (mozzan)]

這是去年公費留學演算法考題

Let A[1..n] and B[1..n] be two sorted (in increasing order) arrays,

each containing n numbers.

Design an O(log n)-time algorithm to find the median of all 2n elements

in arrays A and B. Explain your answer and analyze the complexity.

連結:

http://www.edu.tw/files/site_content/B0003/65%E6%BC%94%E7%AE%97%E6%B3%95.pdf

我的想法是抓A[n/2], B[n/2]出來比較，但細節不知道如何描述，

有人有好的解法嗎??

謝謝分享

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.127.222.204
推 gskman:感覺上Binary search 就可以吧？沒說要合併還是分開找
推 louis719:if(A[n/2]<B[n/2]) 就去找A[n/2~n]以及B[0~n/2]的中位數
→ louis719:if(A[n/2]==B[n/2]) return A[n/2]
→ louis719:if(A[n/2]>B[n/2]) 找A[0~n/2] 以及B[n/2~n]的中位數
→ louis719:time complexity T(n)=2T(n/2)+O(1)
→ louis719:                T(n)=T(n/2)+O(1)才對 打錯
→ bbhands:Cormen的習題
推 mqazz1:老梗題0.0
推 chunhsiang:滿經典的題目