LeetCode Hot100 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
思路
第一次
两次二分查找，先找行，再找列，注意数组不要越界。复杂度上logmn
第二次
当一维数组做，复杂度同logmn
代码
第一遍
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i = 0,j = matrix.size()-1;int m,row;while(i<=j){m = i+ (j-i)/2;if(matrix[m][0] == target)return true;else if(matrix[m][0] > target){j = m-1;}elsei = m+1;}if((row = i-1) < 0)return false;i = 0;j = matrix[0].size()-1;while(i<=j){m = i + (j-i)/2;if(matrix[row][m] == target)return true;else if(matrix[row][m] > target)j = m-1;elsei = m+1;}return false;}
};第二遍
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i = 0,j = matrix.size()*matrix[0].size()-1;int m,size = matrix[0].size();int row,col;while(i<=j){m = i+ (j-i)/2;row = m/size;col = m%size;if(matrix[row][col] == target)return true;else if(matrix[row][col] > target){j = m-1;}elsei = m+1;}return false;}
};