力扣74 搜索二维矩阵

获取矩阵的行数和列数

vector<vector>& matrix

 matrix 是一个 vector<vector> 类型的二维向量，其本质是一个嵌套的动态数组

matrix.size() 返回的是外层 vector 的大小，即有多少个 vector 元素，也就是二维向量的行数

matrix[0] 是第一行的 vector，即第一个 vector 元素
matrix[0].size() 返回第一行的大小，也就是该行中 int 元素的数量，即列数

一维索引与二维坐标的转换

在二维数组中，如果将所有元素按行优先的方式展开为一维数组，那么任意一维索引 mid 对应的二维坐标为：

row = mid / ncol = mid % n

在 C++ 中，数组索引是从 0 开始的

错误代码

class Solution {public: bool searchMatrix(vector<vector>& matrix, int target) { int m=matrix.size(); int n=matrix[0].size(); int left=0; int right=m*n; while(left<=right){ int mid=left+(right-left)/2; int row=mid/n; int col=mid%n; if(targetmatrix[row][col]){ left=mid+1; } else{ return true; } } return false; }};

注意把right初试为m*n-1

正确代码

class Solution {public: bool searchMatrix(vector<vector>& matrix, int target) { int m=matrix.size(); int n=matrix[0].size(); int left=0; int right=m*n-1; while(left<=right){ int mid=left+(right-left)/2; int row=mid/n; int col=mid%n; if(targetmatrix[row][col]){ left=mid+1; } else{ return true; } } return false; }};