在排好序（或者部分排好序）的矩阵上进行搜索是考察多维数组操作和查找的一种经典面试题类型。这里假设行数和列数分别是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)
public 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