Leetcode 240. 搜索二维矩阵 II 矩阵 / 二分

原题链接： Leetcode 240. 搜索二维矩阵 II

解法一：排除法
参考 【图解】排除法，一图秒懂！（Python/Java/C++/C/Go/JS/Rust）

从右上角：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        int n=matrix[0].size();
        int min_num=matrix[0][0];
        int max_num=matrix[m-1][n-1];
        if(target<min_num || target>max_num) return false;
        int i=0,j=n-1;
        while(i<m && j>=0){
            if( matrix[i][j]==target) {
                return true;
            }
            if( matrix[i][j]<target){
                i++;
            }
            else{
                j--;
            }
        }
        return false;
    }
};

从左下角:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        int n=matrix[0].size();
        int min_num=matrix[0][0];
        int max_num=matrix[m-1][n-1];
        if(target<min_num || target>max_num) return false;
        int i=m-1,j=0;
        while(i>=0 && j<n){
            if( matrix[i][j]<target ){
                j++;
            }
            else if( matrix[i][j]>target ){
                i--;
            }
            else return true;
        }
        return false;
    }
};

解法二：二分

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        int n=matrix[0].size();
        int min_num=matrix[0][0];
        int max_num=matrix[m-1][n-1];
        if(target<min_num || target>max_num) return false;
        for(auto row: matrix){
            auto it = lower_bound(row.begin(),row.end(),target);
            if (it != row.end() && *it==target) return true;
        }
        return false;
    }
};