leetcode75:search-a-2d-matrix
题目描述
请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
例如：
对于下面的矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
要搜索的目标值为3，返回true； Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target =3, returntrue.
示例1
输出
复制false
class Solution {
public:
/**
*
* @param matrix int整型vector<vector<>>
* @param target int整型
* @return bool布尔型
*/
bool searchMatrix(vector<vector<int> >& matrix, int target) {
// write code here
int rows=matrix.size();
int cols=matrix[0].size();
int begin=0,end=rows*cols-1;
while (begin <= end)
{
int mid=(begin+end)/2;
int row=mid/cols;
int col=mid%cols;
if (matrix[row][col] ==target)
return true;
else if (matrix[row][col]<target)
begin=mid+1;
else
end=mid-1;
}
return false;
}
};