给定$ n\times n$ 的实数矩阵，每行和每列都是递增的，求这$ n^2$ 个数的中位数。
使用类似 Tarjan 的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性$ O(n\log^2n)$ 。
但是这个问题是有$ O(n)$ 的算法的，在Top Language Google Group的Obtuse Sword 的指点下，找到了这个问题的原始论文：Generalized Selection and Ranking: Sorted Matrices。事实上这篇论文证明了更强的结论：
对于一个$ n\times m$ ($ n\leq m$ )的矩阵，若每行和每列都是递增的，则可以在$ O(n\log2m/n)$ 找到第$ k$ 大的数。
算法的基本思路是将矩阵依次对半划分成更小的子矩阵，然后删除不可能包含所求中位数的子矩阵。通过对每次划分后子矩阵个数的估计，发现此算法时间复杂度为$ O(n\log2m/n)$ 。
使用同样的技巧，可以证明更更强的结论(这个算法具体过程就没细看了):
一堆$ n_i\times m_i$ ($ n_i\leq m_i$ )的矩阵，若每个矩阵的每行和每列都是递增的，则 selection problem （即找第$ k$ 大的数）的时间复杂度为$ O(\sum n_i\log2m_i/n_i)$ 。
Q. E. D.
