题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
出处
思路
矩阵的特点是任意一个位置的数是以其为右下角的子矩阵的最大值，同时是以其为左上角的子矩阵的最小值。所以可以进行二分查找。当target大于某个位置的值时，以这个位置为右下角的矩阵就不用搜了，剩余的部分组成两个新的矩阵。反之同理。
代码
class Solution {
private:
bool _2D_search(vector<vector<int>>& matrix, int target, int x1, int y1, int x2, int y2){
if(x1+1>=x2 || y1+1>=y2){
for(int i=x1; i<=x2; i++)
for(int j=y1; j<=y2; j++)
if(matrix[i][j]==target)
return true;
return false;
}
int mid_x=(x1+x2)/2,mid_y=(y1+y2)/2;
if(target==matrix[mid_x][mid_y])
return true;
else if(target>matrix[mid_x][mid_y])
return _2D_search(matrix,target,x1,mid_y,x2,y2) || _2D_search(matrix,target,mid_x,y1,x2,mid_y);
else
return _2D_search(matrix,target,x1,y1,x2,mid_y) || _2D_search(matrix,target,x1,mid_y,mid_x,y2);
}
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m=matrix.size();
int n=matrix[0].size();
int mi=min(m,n);
if(matrix[0][0]==target || matrix[m-1][n-1]==target)
return true;
if(matrix[0][0]>target || matrix[m-1][n-1]<target)
return false;
return _2D_search(matrix,target,0,0,m-1,n-1);
}
};
