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;}
};