题干
请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征： 每一行的数字都从左到右排序 每一行的第一个数字都比上一行最后一个数字大
用例
例如对于下面矩阵：
代码语言：javascript复制[
[1, 3, 5, 9],
[10, 11, 12, 30],
[230, 300, 350, 500]
]要搜索的目标值为3，返回true； 示例1 输入：
代码语言：javascript复制[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3返回值：
代码语言：javascript复制true解答
有效信息：
- 每一行的数字都从左到右递增
- 每一行的第一个数字都比上一行最后一个数字大
故此此矩阵有序，可用二分查找取值。
方法一：两次二分查找
可以先通过二分查找确定 行，再对该 行 继续进行二分查找 ，常规思维：
代码语言：javascript复制class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rowIndex = binarySearchFirstColumn(matrix, target);
if (rowIndex < 0) {
return false;
}
return binarySearchRow(matrix[rowIndex], target);
}
public int binarySearchFirstColumn(int[][] matrix, int target) {
int low = -1, high = matrix.length - 1;
while (low < high) {
int mid = (high - low 1) / 2 low;
if (matrix[mid][0] <= target) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
}
public boolean binarySearchRow(int[] row, int target) {
int low = 0, high = row.length - 1;
while (low <= high) {
int mid = (high - low) / 2 low;
if (row[mid] == target) {
return true;
} else if (row[mid] > target) {
high = mid - 1;
} else {
low = mid 1;
}
}
return false;
}
}复杂度分析
时间复杂度：
其中 mm 和 nn 分别是矩阵的行数和列数。
空间复杂度：
方法二：一次二分查找
因为每一行的第一个数字都比上一行最后一个数字大 ，所以我们可通过 数学的方法 将其压缩为一个 一维矩阵
代码语言：javascript复制import java.util.*;
public class Solution {
/**
*
* @param matrix int整型二维数组
* @param target int整型
* @return bool布尔型
*/
public boolean searchMatrix (int[][] matrix, int target) {
// write code here
int M = matrix.length, N = matrix[0].length,left = 0, right = M * N - 1;
while (left <= right) {
int center = ( right - left) / 2 left;
int compute = matrix[center / N][center % N];
if (compute < target) {
left = center 1;
} else if (compute > target) {
right = center - 1;
} else {
return true;
}
}
return false;
}
}复杂度分析
时间复杂度：O(logmn)，其中 m是矩阵的行 和 n 是矩阵的列 空间复杂度：O(1)，原有数组上进行操作，未申请额外空间
