[理工] 演算法一題:2個sorted array找median

[ff00662299 (Broken Coastline)]

給兩個sorted array A跟B，
A的長度是m，B的長度是n。
想問為什麼要找這m+n個數的median的時間可以做到log min(m,n)?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.233.76 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1671195049.A.C69.html
推 A4P8T6X9: binary search 任一 array，每次取中點代表該  array
謝謝A大！很完整的說明
→ A4P8T6X9: 要貢獻多少個數字到合併後的陣列的左邊，因為有兩個陣
→ A4P8T6X9: 列的長度，另外一個陣列要貢獻多少個數字可以直接算出
→ A4P8T6X9: 來，之後如果貢獻出來的左邊的值大於另外一半右邊的值
→ A4P8T6X9: ，代表這個切法錯誤，需要調整，基本上調整方式會根據
→ A4P8T6X9: 剛剛貢獻出來的左邊數字進行調整。因為除了 binary sea
→ A4P8T6X9: rch 以外都是常數時間，且可以任選一個 array 做，所以
→ A4P8T6X9: 是 log(min(m, n))
※ 編輯: ff00662299 (49.216.164.99 臺灣), 12/17/2022 22:50:46
推 a93011abc: 設較長的陣列為m拿m[m+n/2]去跟n[i]比；i=0~n。若n較大
→ a93011abc: 結束n較小i+的同時m陣列往前一格 所以最多會走n個
→ lingege321: Leetcode第四題 可以查