problem：
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.
Hide Tags
Array Binary
Search
题意：给定1个矩阵：每行递增，每列递增，查找target是不是在该矩阵中
thinking：
经典2分法的时间复杂度为 log（m）+log(n)=log（m*n）
（1）2分法查找锁定target在矩阵的哪1行
（2）2分法查找target是不是在锁定的那1行
code：
2分法：时间复杂度为log（m）+log(n)=log（m*n）
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int m=matrix.size();
int n=matrix[0].size();
int index=binary_search_1(matrix,target,0,m⑴);
if(index<0 || index>=m)
return false;
return binary_search_2(matrix[index],target,0,n⑴);
}
protected:
int binary_search_1(vector<vector<int> > &matrix, int target, int start, int end)
//锁定target所在行
{
if(start>=end)
return start;
int mid=(start+end)/2;
if(target>=matrix[mid][0]&&target<matrix[mid+1][0])
return mid;
else if(target<matrix[mid][0])
return binary_search_1(matrix,target,start,mid⑴);
else
return binary_search_1(matrix,target,mid+1,end);
}
bool binary_search_2(vector<int> &a, int target, int start, int end)
//在锁定行中查找target
{
if(start>=end)
return a[start]==target;
int mid=(start+end)/2;
if(a[mid]==target)
return true;
else if(a[mid]<target)
return binary_search_2(a,target,mid+1,end);
else
return binary_search_2(a,target,start,mid⑴);
}
};
还有1个不错的算法，时间复杂度为O（m+n）：
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int i = 0, j = matrix[0].size() - 1;
while (i < matrix.size() && j >= 0)
{
if (target == matrix[i][j])
return true;
else if (target < matrix[i][j])
j--;
else
i++;
}
return false;
}
};