题目
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
代码与注释
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = n<=0?0:matrix[0].length;
//判断数组是否为0；判断是否在数组数值范围内
if(n == 0|| m==0||matrix[0][0]>target || matrix[n-1][m-1]<target){
return false;
}
int left = 0;
int right = n-1;
int mid;
//二分查找法，找到相关的行
while(right > left){
mid = (left + right)/2;
if(matrix[mid][0] == target){
return true;
}else if(matrix[mid][0] > target){
right = mid -1;
}else{
left = mid +1;
}
}
//进行调整，获取所在的行
int row = matrix[right][0]>target?right-1:right;
left= 0;
right = m-1;
//用二分查找法获取target在所在列的具体位置
while(right > left){
mid = (left + right)/2;
if(matrix[row][mid] == target){
return true;
}else if(matrix[row][mid] > target){
right = mid -1;
}else{
left = mid +1;
}
}
//排除单列或者单行的情况
return target == matrix[row][right];
}
}
