请写出一个高效的在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)，原有数组上进行操作，未申请额外空间
