主要内容 #

1. 搜索二维矩阵
2. 求解思路1
3. 求解思路2
4. 参考代码

1. 搜索二维矩阵 #

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例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

2. 求解思路1 #

由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是升序的。
因此我们可以使用两次二分来定位到目标位置：

• 第一次二分：从第 0 列中的「所有行」开始找，找到合适的行 row
• 第二次二分：从 row 中「所有列」开始找，找到合适的列 col
• 技巧：在搜索所在行的时候，以最后一列的值与target大小作为收缩边界的判断依据

3. 求解思路2 #

若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。
代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。

4. 参考代码 #

思路1代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) {
            return false;
        }
        int row = matrix.size();
        int col = matrix[0].size();
        //二分查找行数
        int up = 0;
        int down = row - 1;
        while(up < down) {
            int mid = up + (down - up) / 2;
            if(matrix[mid][col-1] < target) {  //这一行的最后一个值比target还要小，收缩上边界
                //下一轮搜索范围[mid + 1， down]
                up = mid + 1;
            } else {
                down = mid;
            }
        }
        //二分查找所在列
        int left = 0;
        int right = col - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(matrix[up][mid] < target) { //mid<target，收缩左边界
                //下一轮搜索范围[mid+1,right]
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if(matrix[up][left] == target) {
            return true;
        }
        return false;
    }
};

思路2代码

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