在排好序（或者部分排好序）的矩阵上进行搜索是考察多维数组操作和查找的一种经典面试题类型。这里假设行数和列数分别是M和N。下面根据难度来总结一下几个不同的题目变体：
1. LeetCode原题 Search a 2D Matrix：
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true.
这题非常的基础，特别简单，因为题目对排序的要求特别的严格，整个矩阵按行完全排好序。利用排序性质，二分搜索的思路非常清晰。
思路1：首先二分搜索确定行号，然后再二分搜索确定列号。
public boolean Find(int[][] matrix, int elem) {
// binary search the row number
int low, high, mid = 0;
low = 0;
high = matrix.length - 1;
while (low <= high) {
mid = low + (high - low) / 2;
if (matrix[mid][0] == elem) {
return true;
} else if (matrix[mid][0] > elem) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// make sure the row starts with a number less than the target element
if (matrix[mid][0] > elem) {
mid--;
}
int row = mid;
// binary search the column number
low = 0;
high = matrix[0].length - 1;
while (low < high) {
mid = low + (high - low) / 2;
if (matrix[row][mid] == elem) {
return true;
} else if (matrix[row][mid] > elem) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
因为使用了两次二分搜索，时间复杂度为O(logM + logN)。
思路2：由于整个矩阵完全排好序，其实可以直接把这个二维数组看成一个M*N大小的一维数组，这样一次二分搜索就可以了。代码更加简洁。
public boolean find(int[][] matrix, int target) {
int numRows = matrix.length;
if (numRows == 0) return false;
int numCols = matrix[0].length;
int low = 0, high = numRows * numCols - 1;
int mid, col, row;
while (low <= high) {
mid = low + (high - low) / 2;
col = mid % numCols;
row = mid / numCols;
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
时间复杂度是log(M * N) = logM + logN。所以效率和思路1完全一样。
2. CareerCup原题：
Given a matrix in which each row and each column is sorted, write a method to find an element in it.
注意这题和第一题的区别在于：尽管矩阵内的每行和每列都排好序了，但是整个矩阵并不是完全按行排序的。一个简单例子就是在矩阵{ { 0, 1, 4 }, { 1, 2, 5 }, { 2, 3, 6 } }中搜索4。如果直接使用上一题的思路，会导致找不到，因为前面行的后面元素允许大于后面行的前面元素。所以，如果想提高搜索效率，需要首先找到矩阵内完全排序的子区域。那么完全排好序的子区域是什么呢？
因为每行排好序，每列也排好序，对于任意一个元素，元素所在行的左边元素肯定都小于自己，而且元素所在列的下边元素也肯定都小于自己。由此可知，对于任意一个元素，所在的完全排序子区域就是该元素同行左边+该元素自身+该元素同列下边。
1. 思路1：(CareerCup给出的标准解法)
沿着对角线进行线性查询：因为每行和每列都排好序，以矩阵右上角为起点，沿着对角线扫描。
1）如果该元素等于目标元素，则找到目标；
2）如果该元素大于目标元素，则可以排除当前列，坐标往左移1个单位；
3）如果该元素小于目标元素，则可以排除当前行，坐标往下移1个单位。
public boolean find(int[][] matrix, int elem) {
// start from the top right element
int row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == elem) {
return true;
} else if (matrix[row][col] > elem) {
col--;
} else {
row++;
}
}
return false;
}
注意我看的CareerCup版本里给出的标答有写小疏漏，把循环条件里的col >= 0写成了col > 0，这样的话，在矩阵{ { 0, 1, 3 }, { 1, 3, 5 }, { 4, 5, 6 } }中查找4是会找不到的，因为4作为行首元素会被漏掉。
这个思路没有利用二分搜索，而是沿着对角线不断对搜索区域根据部分排序性质进行排除，时间复杂度为O(M+N)。
思路2：（LeetCode讨论版块给出的答案）
既然只有部分的排序，那么也可以只进行部分的二分搜索，从而试图进一步优化。
// binary search in a given row, starting from the first column and ending
// with a given ending column index (inclusive)
private int binarySearchInRow(int[][] matrix, int row, int endCol,
int elem) {
int low = 0, high = endCol, mid = 0;
while (low <= high) {
mid = low + (high - low) / 2;
if (matrix[row][mid] == elem) {
return mid;
} else if (matrix[row][mid] > elem) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// make sure the matrix[row][mid] value is greater than the target
// element
if (matrix[row][mid] < elem && mid < endCol) {
mid++;
}
// differentiate from the case when the target element is the first element in the row
if (mid == 0) {
return Integer.MAX_VALUE * -1;
}
return -1 * mid;
}
// binary search along diagonal: complexity O(M * logN)
public boolean find(int[][] matrix, int elem) {
// start from the top right element
int row = 0, col = matrix[0].length - 1;
// binary search via the diagonal
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == elem) {
return true;
} else if (matrix[row][col] > elem) {
// binary search the current row ahead of the current column
int retCol = binarySearchInRow(matrix, row, col, elem);
if (retCol >= 0) {
return true;
} else {
col = retCol * -1;
if (col == Integer.MAX_VALUE)
return false;
row++;
}
} else {
row++;
}
}
return false;
}
与第一个思路相比，唯一的区别在于循环内的第二个分支使用了二分搜索，如果在当前行内没有找到目标元素，就会寻找当前行内刚好大于目标元素的数，并且返回该坐标值的相反数。返回相反数是为了区别找到和没找到两种情况，找到的话返回坐标值，为非负数，没找到返回坐标值的相反数，为负数。注意如果当前行的第一个元素都大于目标元素，则说明继续下去也无法找到，我这时返回了一个整数最大值的相反数。当然，最好的做法是返回坐标值和是否找到两个值，需要传引用，不过用Java写不是太方便（除非申明成员变量）。
简单的说，如果在当前没有找到，可以一次性排除当前行和多列，而思路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之间的大小关系。后两种思路太复杂，我觉得前两种思路作为面试题的解法足够了。