74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
-每行中的整数从左到右按升序排列。
-每行的第一个整数大于前一行的最后一个整数.
示例一：
1
2
| 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
|
示例二：
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;
}
};
|
