题目：
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路：
二分法。
- 先获取当前矩阵的最大值和最小值，即左上角的值和右下角的值
为(x1,y1)和(x2,y2)。当x1 = x2 且 y1 = y2时，说明矩阵为一个点。 - 求mid值，即 ( (x1+x2)/2 , (y1+y2)/2 )
- 将mid值与target进行比较，来决定接下来取查询那些范围
· 如果target = mid 说明找到了目标值
· 如果target < mid，说明以mid为最小值的那块矩阵，不会有target， target在其他范围
· 如果target > mid，说明以mid为最大值的那块矩阵里，不会有target， target在其他范围里面 - 接下来对其他范围进行递归查询
代码：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length < 1 || matrix[0] == null || matrix[0].length < 1) {
return false;
}
return searchMatrix(matrix,target,0,0,matrix.length-1,matrix[0].length-1);
}
//方法
private boolean searchMatrix(int[][] matrix, int target, int x1, int y1, int x2, int y2) {
if(x2 < x1 || y2 < y1){
return false;
}
if(target < matrix[x1][y1] || target > matrix[x2][y2]){//若果小于矩阵最小值，或者大于矩阵最大值，直接返回false。
return false;
}
int mid_x = (x1 + x2) / 2;
int mid_y = (y1 + y2) / 2;
if(target == matrix[mid_x][mid_y]){
return true;
}
if(target < matrix[mid_x][mid_y]){ //target不在第四象限
return (
//查找第二象限
searchMatrix(matrix,target,x1,y1,mid_x-1,mid_y-1) ||
//查找第一象限
searchMatrix(matrix,target,x1,mid_y,mid_x-1,y2) ||
//查找第三象限
searchMatrix(matrix,target,mid_x,y1,x2,mid_y-1)
);
}else { //target不在第二象限
return (
//查找第四象限
searchMatrix(matrix, target,mid_x+1,mid_y+1,x2,y2) ||
//查找第一象限
searchMatrix(matrix,target,x1,mid_y+1,mid_x,y2) ||
//查找第三象限
searchMatrix(matrix,target,mid_x+1,y1,x2,mid_y)
);
}
}
}
但是我看其他人提交的代码，思路是从左下 或者 右上开始遍历。
思路是：
从左下角角标开始查找
如果>target 则向上移动角标
如果<target 则向右移动角标
如果==target 则返回True
如果角标出界还没找到target 则返回False
但是我认为这种不是最优的，比如二维数组只有一行或者一列的话，这就是一次时间复杂度为O(n)的遍历。
代码如下（代码是从右上角开始的）
class Solution {
public boolean searchMatrix(int[][] matrix, int target){
if (matrix.length==0)
return false;
int i = matrix.length-1,j=0;
while(i>=0 && j<matrix[0].length){
if (matrix[i][j] == target)
return true;
else if(matrix[i][j]>target)
i--;
else if(matrix[i][j]<target)
j++;
}
return false;
}
}