74. 搜索二维矩阵
3 min
题目
解法：二分查找
思路
将二维矩阵视为一维有序数组，应用二分查找。
由于矩阵每行内部有序且行间首尾相接严格递增，整体可线性化为严格递增序列，二分查找能准确定位任意元素而不遗漏最优解。
- Step 1: 计算矩阵总长度 mn，初始化左右指针 left=0, right=mn-1
- Step 2: 循环二分，计算中间索引 mid = (left + right) / 2
- Step 3: 将 mid 转换为二维坐标 (mid/n, mid%n) 获取对应值
- Step 4: 比较 val 与 target，调整左右指针范围
- Step 5: 找到返回 true，否则循环结束返回 false
复杂度
- 时间复杂度:
- 空间复杂度:
代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int left = 0, right = m*n - 1;
while(left <= right){
int mid = (left + right) / 2;
int val = matrix[mid / n][mid % n];
if(val == target) return true;
else if(val < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
};