简单的说，如果在当前没有找到，可以一次性排除当前行和多列，而思路1一次只能排除一列。
这个思路看似得到了优化，其实反而增加的时间复杂度。根据LeetCode版主的分析（http://leetcode.com/2010/10/searching-2d-sorted-matrix.html），如果M=N，那么这题的时间复杂度是O(logN!)。其实这个值近似于O(M*logN)。最坏情况是每行都做了一次二分搜索，但每次都返回的是搜索当前行的行尾元素。这样看来，这个算法本质上和对每行进行一次二分搜索没太大区别。
注意，在此基础上对循环内的第三个分支进行二分搜索优化是不可行的，否则跟第一题的解法没什么区别了。
3. Google面试题：
Given a M * N Matrix. All rows are sorted, and all columns are sorted. Find the Kth smallest element of the matrix.
这题有种错误做法是以第一个元素为起点（因为必定为最小元素），构造一个最小堆，每次将从第一行第i个元素到第一列第i个元素这条线上的所有元素，插入到堆中。直到堆的大小大于或等于K。然后再做K-1次删除最小元素操作，结果就为最小当前元素。
这样的做法是错误的，因为任意一行的所有元素都可以比下一行的第一个元素小，很简单的例子就是{ {1, 2, 3}, {4, 5, 6} }，如果K=3，那么结果应该返回3而不是4。
思路1：利用QuickSelect算法
经典的QuickSelect算法（http://en.wikipedia.org/wiki/Quickselect youtube.com/watch v=kcVk30zzAmU）可以在线性时间内找到一维数组内的第K个元素。如果这里忽略已有的排序性质，把这个矩阵当成一个乱序的1维数组，那么直接利用QuickSelect算法可以得到O(M*N)的解。
思路2：利用部分排序的性质和最小堆
如果使用最小堆，如何使得插入的次数最少呢？换句话说，我们应该只插入需要插入的元素，或者说”刚好“只比当前元素大一点的元素。按照这个思路，我们仍然应该以第一个元素作为起点。
那么对于任意一个元素，“刚好”比它大一点的元素有哪些呢？
1.右边邻居；
2.下边邻居；
3.下边邻居的某些左侧元素。
前两种情况比较直观，第三种情况就只有靠标记了。具体做法如下：
初始化将第一个元素放入最小堆中。
1）每次弹出当前堆中的最小值，并将其右邻居和下邻居插入堆中，并标额外记右邻居和下邻居已经在堆中。如果之前某邻居已经被标记，则不再处理；（注意下邻居很可能之前是某元素的右邻居，要避免重复处理）
2）如果弹出的元素总数为K，则停止。
按照这个思路，处理K个元素最多也就将2K个元素插入堆中，堆的大小不超过2K，，所以算法复杂度是O(K*logK)。
思路3：O(M+N)算法
http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf
思路4：Frederickson和Johnson实现的O(K)算法
Greg N. Frederickson and Donald B. Johnson. Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13, pp. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1 isAuthorized=no
算法选择需要看实际情况，取决于K和M，N之间的大小关系。后两种思路太复杂，我觉得前两种思路作为面试题的解法足够了。