题目
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, return true.
分析
给出一个矩阵，寻找一个值是否存在。由于每一行都是顺序排列的，直接二分法即可。我感觉比较简单，不知道为啥难度为中级。
其他人的算法是从右上角向左下方一步一步的搜索，直到找到需要值。
bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) {
bool ans=false;
for(int i=0;i<matrixRowSize;i++)
{
if(matrix[i][0]>target||matrix[i][matrixColSize-1]<target)
continue;
int p=0,q=matrixColSize-1;
while(p<=q)
{
//printf("%d %d\n",p,q);
int temp=(p+q)/2;
if(matrix[i][temp]==target)
{
ans=true;
return ans;
}
else if(matrix[i][temp]>target)
{
q=temp-1;
}
else
{
p=temp+1;
}
}
}
return ans;
}
