sorted matrix ( Young Matrix )
search for a given value in the matrix:
1) starting from upper-right corner, turn left or turn down, O(n+m)
2) if it‘s square, O(n+m) is optimal, see http://stackoverflow.com/a/10597806
3) if it‘s not square, e.g. in extreme case it degenerates to a sorted array, the complexity is lower-bounded to O(m*(1+log(n/m)) (suppose m < n)
4) page http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster has more details
find k-th element in the matrix: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
a) heap-based, starting from top-left corner element, push to heap; each time an element is poped, push its right and down elements.
complexity is k*log(k)
b) binary-search on target value, starting from [smallest, largest], and then count how many elements are less than this value to see if it‘s kth element. O(n*log(n)*log(N)) where n is number of rows, N is (largest-smallest)
sorted matrix - search & find-k-th
原文：http://www.cnblogs.com/qsort/p/6045245.html