74、搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 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
【思路】
由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
//非二分查找法 class Solution { public boolean searchMatrix(int[][] matrix, int target) { int i = 0; for (i = matrix.length - 1; i > 0 ; i--) { if (matrix[i][0] <= target) { break; } } for (int j = 0; j < matrix[i].length; j++) { if (matrix[i][j] == target) return true; } return false; } }
//改为二分查找的方式来做
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; //用原来的也可以 //int mid = (high + low) / 2; if (row[mid] == target) { return true; } else if (row[mid] > target) { high = mid - 1; } else { low = mid + 1; } } return false; } }
