※ 引述《DJWS (...)》之銘言：
: FRAXIS 這是你的文章嗎？
: http://algnotes.wordpress.com/2014/10/09/
哈，被發現了。
: 看完這個我就想通了
: 行列已排序的陣列，可以用階梯狀移動的方法找rank（做partition），O(n)
: 只有行排序的陣列，可以用 n 次 binary search 找 rank (做partition)，O(n log n)
: 所以是 O(log n) 回合沒錯
: 行列已排序是 O(n logn)
: 只有行排序是 O(n logn logn)
其實我之前還想到一個變形，就是給定常數個排序陣列找第 k 位。
如果套用行排序的方法，會需要O(lg^2 n)。
但是我們知道兩個陣列找中位數只需要O(lg n)的時間。
不過如果用我之前說的方法，找中位數就只需要O(lg n)的時間了。
: 最後我還是想問，學術界有人做過這個題目嗎？
: 還是說文章中的 reference paper 就是這個方法？
: 我想整理到演算法筆記上面
那篇paper是講行列排序時O(n)的方法。
只有行排序的方法，我也有找到一些資料。
http://algnotes.wordpress.com/2010/05/30/finding-median-in-3-arrays/