一、题目描述
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -10^4 <= matrix[i][j], target <= 10^4
二、解题思路
由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。
我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
三、代码
代码语言：javascript复制public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n=matrix.length;
int m=matrix[0].length;
int row=binarySearchRow(matrix,target);
if(row==-1){
return false;
}
int column=binarySearchColumn(matrix[row],target);
if(column==-1){
return false;
}
return true;
}
int binarySearchRow(int[][] matrix, int target){
int low=0,high=matrix.length-1;
while(low<=high){
if(low==high){
return low;
}
int mid=(high low)/2;
if(matrix[mid][0]<=target && matrix[mid 1][0]>target){
return mid;
}
if(matrix[mid][0]<target){
low=mid 1;
}
if(matrix[mid][0]>target){
high=mid-1;
}
}
return -1;
}
int binarySearchColumn(int[] array, int target){
int low=0,high=array.length-1;
while(low<=high){
int mid=(high low)/2;
if(array[mid]==target){
return mid;
}
if(array[mid]<target){
low=mid 1;
}
if(array[mid]>target){
high=mid-1;
}
}
return -1;
}
public static void main(String[] args) {
//int[][] matrix={{1,3,5,7},{10,11,16,20},{23,30,34,60}};
int[][] matrix={{1}};
Solution solution=new Solution();
Boolean bool=solution.searchMatrix(matrix,1);
System.out.println(bool);
}
}四、复杂度分析
时间复杂度：O(logm logn)=O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。
空间复杂度：O(1)。
