43 搜索二维矩阵

43 搜索二维矩阵

43.1 搜索二维矩阵解决方案

解决思路：

• 将二维矩阵映射为一维数组的形式：
  • 如果矩阵有m行和n列，那么二维矩阵的下标(row,col)可以通过以下公式映射为一维下表index：$index=row\times n+col$
  • 反之，如果有一维下表index，可以通过以下公式还原为二维下标(row,col)：$row=index//n,col=index\%n$
• 使用二分查找：
  • 将左指针left初始化为0，右指针right初始化为矩阵元素总数减1.
  • 通过上述公式找到当前中间位置mid对应的二维矩阵元素，并与目标值进行比较。
  • 根据根据比较结果更新左右指针，直到目标值或搜索范围为空。

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.