题干
请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
用例
例如对于下面矩阵：
[
[1, 3, 5, 9],
[10, 11, 12, 30],
[230, 300, 350, 500]
]
要搜索的目标值为3，返回true；
示例1
输入：
[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3
返回值：
true
解答
有效信息：
每一行的数字都从左到右递增
每一行的第一个数字都比上一行最后一个数字大
故此此矩阵有序，可用二分查找取值。
方法一：两次二分查找
可以先通过二分查找确定 行，再对该 行 继续进行二分查找 ，常规思维：
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;
}
}
复杂度分析
时间复杂度：
O ( log m + log n ) = O ( log m n ) O ( l o g m + l o g n ) = O ( l o g m n ) O(\log m+\log n)=O(\log mn)O(logm+logn)=O(logmn)O(logm+logn)=O(logmn)O(logm+logn)=O(logmn)
其中 mm 和 nn 分别是矩阵的行数和列数。
空间复杂度：O ( 1 ) O(1)O(1)。
方法二：一次二分查找
因为每一行的第一个数字都比上一行最后一个数字大 ，所以我们可通过 数学的方法 将其压缩为一个 一维矩阵
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)，原有数组上进行操作，未申请额外空间
