74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
-每行中的整数从左到右按升序排列。
-每行的第一个整数大于前一行的最后一个整数.
示例一:
![](https://assets.leetcode.com/uploads/2020/10/05/mat.jpg)
1 2
| 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出:true
|
示例二:
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/mat2.jpg)
1 2
| 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出:false
|
提示:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
使用二分法,然后剪枝,对于每一行使用二分法,当target比当前行数尾的数还大时,直接去下一行搜寻。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); int n = matrix[0].size();
for(int i = 0 ; i < m ; i++) { if(target > matrix[i][n - 1])continue; int left = 0; int right = n - 1; while(left <= right) { int mid = left + ((right - left) / 2); if(matrix[i][mid] == target)return true; else if (matrix[i][mid] > target){ right = mid - 1; } else if(matrix[i][mid] < target){ left = mid + 1; } } } return false; } };
|