28. Search a 2D Matrix
public:
/**
* @param matrix: matrix, a list of lists of integers
* @param target: An integer
* @return: a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int>> &matrix, int target) {
// write your code here
// binary search 1，先找比target小的最大的值 2，然后在这一行内找。复杂度是O(log(m) + log(n))
const int m = matrix.size();
if(m == 0){
return false;
}
const int n = matrix[0].size();
if(target < matrix[0][0]){
return false;
}
if(target > matrix[m - 1][n - 1]){
return false;
}
int start = 0;
int end = m - 1;
int row = 0;
while(start + 1 < end){
int mid = start + (end - start) / 2;
if(matrix[mid][0] == target){
return true;
}
else if(matrix[mid][0] < target){
start = mid;
}
else{
end = mid;
}
}
if(matrix[end][0] <= target){
row = end;
}
else if(matrix[start][0] <= target){
row = start;
}
start = 0;
end = n - 1;
while(start + 1 < end){
int mid = start + (end - start) / 2;
if(matrix[row][mid] == target){
return true;
}
else if(matrix[row][mid] < target){
start = mid;
}
else{
end = mid;
}
}
if(matrix[row][start] == target){
return true;
}
else if(matrix[row][end] == target){
return true;
}
else{
return false;
}
}
Comments
Post a Comment