※ 引述《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/