1.问题描述
给你一个满足下述两条属性的 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
提示
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
难度等级
中等
题目链接
搜索二维矩阵
2.解题思路
这道搜索二维矩阵的题比较常规，话不多说，直接开干。
因为这是一个已经排好序的二维矩阵，每一行的第一个整数一定大于上一行的所有整数，所以我们可以先判断target是否在这个矩阵内，再进行搜索。如果target小于矩阵中最小的数或者target大于矩阵中最大的数，那就不用搜索了，肯定不在。
java"> //判断target是否小于矩阵中最小的数if(matrix[0][0] > target){return false;}//判断target是否大于矩阵中最大的数if(matrix[matrix.length-1][matrix[0].length-1] < target){return false;}接着，我们根据矩阵递增的特征，通过比较每一行的最后一个数与target的大小关系，可以定位到target可能处于矩阵的哪一行，用一个循环不断比较，当出现第一个大于或等于target的数时，target就处在那个数所在的行。
java"> //判断target可能位于哪一行矩阵中int row = 0;while(row < matrix.length && matrix[row][matrix[0].length-1] < target){row++;}然后，就是对我们找到的这一行进行常规的二分查找了，设置左右指针和二分指针，不断比较二分值与target的关系，不断缩小查找的范围，直到最终找到target的位置或者左右指针越界。
java"> //左右指针和二分指针int left = 0;int right = matrix[row].length - 1;int mid = 0;//判断target是否真的在我们筛选出来的矩阵中while(left <= right){//更新二分指针mid = (right - left) / 2 + left;//判断中间值是否为我们要找的数if(matrix[row][mid] == target){return true;}//若中间值小于目标值if(matrix[row][mid] < target){left = mid + 1;}//若中间值大于目标值if(matrix[row][mid] > target){right = mid - 1;}}最后，根据查找结果返回对应的答案即可。
3.代码展示
java">class Solution {public boolean searchMatrix(int[][] matrix, int target) {//判断target是否小于矩阵中最小的数if(matrix[0][0] > target){return false;}//判断target是否大于矩阵中最大的数if(matrix[matrix.length-1][matrix[0].length-1] < target){return false;}//判断target可能位于哪一行矩阵中int row = 0;while(row < matrix.length && matrix[row][matrix[0].length-1] < target){row++;}//左右指针和二分指针int left = 0;int right = matrix[row].length - 1;int mid = 0;//判断target是否真的在我们筛选出来的矩阵中while(left <= right){//更新二分指针mid = (right - left) / 2 + left;//判断中间值是否为我们要找的数if(matrix[row][mid] == target){return true;}//若中间值小于目标值if(matrix[row][mid] < target){left = mid + 1;}//若中间值大于目标值if(matrix[row][mid] > target){right = mid - 1;}}//若循环结束还是没有找到，说明target不在矩阵中return false;}
}4.总结
这道题，如果对二分查找熟练的话，其实理解起来不难，要做出来也不难，只要定位到target在矩阵的哪一行，就变成了常规的二分查找了。这道题就简单水到这里，祝大家刷题愉快，早日拿到心仪的offer~
