[数据结构与算法]LeetCode 74. 搜索二维矩阵

题目

题解

• 二分查找

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        int n=matrix[0].size();
        for(int i=0;i<min(m,n);i++){
            int l,r;
            //行
            l=i;r=n-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(matrix[i][mid]==target)
                    return true;
                else if(matrix[i][mid]>target)
                    r=mid-1;
                else if(matrix[i][mid]<target)
                    l=mid+1;
            }

            //列
            l=i;r=m-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(matrix[mid][i]==target)
                    return true;
                else if(matrix[mid][i]>target)
                    r=mid-1;
                else if(matrix[mid][i]<target)
                    l=mid+1;
            }
        }
        return false;
    }
};