描述
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。
样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
挑战
O(log(n) + log(m)) 时间复杂度
思路
由于二维数组是按照严格的升序排列的，所以本题两种解法：
代码
- 先对矩阵的行进行模板二分法来求确定target处于哪一行，然后再对矩阵的列进行二分法, 确定位置。
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
if (matrix == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int column = matrix[0].length;
int start = 0;
int end = row - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[mid][0] == target) {
return true;
}
if (matrix[mid][0] < target) {
start = mid;
}
if (matrix[mid][0] > target) {
end = mid;
}
}
if (matrix[end][0] <= target) {
row = end;
}
else if (matrix[start][0] <= target) {
row = start;
}
/* 此处应注意,不能把else if 写成if 因为多个if是连续执行的，而数组中元素是升序排列的
* matrix[end][0], >= matrix[start][0]的, 若不加else可能会出现row = end 却被
* row = start 覆盖的情形
*/
else {
return false;
}
start = 0;
end = column - 1;
// start,end 前不能加int，因为前面已经定义过start和end了，
// 变量可以重新赋值，但不能重新定义
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (matrix[row][mid] == target) {
return true;
}
if (matrix[row][mid] < target) {
start = mid;
}
if (matrix[row][mid] > target) {
end = mid;
}
}
if (matrix[row][end] == target) {
return true;
}
if (matrix[row][start] == target) {
return true;
}
return false;
}
}
- Binary Search Once
public class Solution {
/**
* @param matrix, a list of lists of integers
* @param target, an integer
* @return a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
if (matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int column = matrix[0].length;
int start = 0, end = row * column - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
// 关键代码
int number = matrix[mid / column][mid % column];
if (number == target) {
return true;
} else if (number > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
}