43 搜索二维矩阵
43.1 搜索二维矩阵解决方案
解决思路:
- 将二维矩阵映射为一维数组的形式:
- 使用二分查找:
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty() || matrix.[0].empty()){return false; // 边界条件,处理空矩阵}int m = matrix.size(); // 矩阵的行数int n = matrix[0].size(); // 矩阵的列数int left =0, right = m * n - 1; // 二分查找的范围while (left <= right){int mid = left + (right - left) / 2; // 防止溢出int midValue = matrix[mid / n][mid % n]; // 映射到二维矩阵if (midValue == target){return true;// 找到目标值} else if(midValue < target){left = mid + 1; // 缩小范围到右侧} else {right = mid - 1; // 缩小范围到左侧}}return false;// 没找到目标值}
};
43.2 举例说明
输入:
matrix = {{1, 3, 5, 7},{10, 11, 16, 20},{23, 30, 34, 60}
};
target = 3;
- 初始
left = 0,right = 11
(总共12个元素)。 - 计算
mid = 5
,对应值为matrix[1][1] = 11
,大于target
,跟新right = 4
. - 计算
mid = 2
,对应值为matrix[0][2] = 5
,大于target
,更新right = 1
. - 计算
mid = 1
,对应值为martix[0][1] = 3
,等于target
,返回true
.