题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

样例

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

算法1

(二分) $O(k(\log n + \log m))$

1. 初始化上下左右边界 up, down, left, right，保证 target 可能出现在此区域。
2. 每次在 up 行中，二分求出新的 right；在 down 行中，二分求出新的 left；
3. 接着在 2 求出的 left 列中，二分求出新的 down；在 2 求出的 right 列中，二分求出新的 up；
4. 如果 up == down && left == right，则判断 matrix[up][left] == target。
5. 注意，如果一轮迭代更新中，四个元素的值都没有变化，则说明那一片区域有多个 target，直接返回 true。

时间复杂度

• 每次迭代时间复杂度为 $O(\log n + \log m)$，假设需要 $k$ 次迭代，故时间复杂度为 $O(k(\log n + \log m))$。
• 最坏情况可能 $k = \min(n, m)$，但平均情况下很难达到最坏情况。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0)
            return false;

        int n = matrix[0].size();

        if (n == 0)
            return false;

        int up = 0, down = m - 1, left = 0, right = n - 1;
        int l, r;
        while (up < down || left < right) {
            int new_left, new_right, new_up, new_down;
            /*********************/
            l = left; r = right;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (target >= matrix[up][mid + 1])
                    l = mid + 1;
                else
                    r = mid;
            }
            new_right = l;
            /*********************/

            /*********************/
            l = left; r = right;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (target <= matrix[down][mid])
                    r = mid;
                else
                    l = mid + 1;
            }
            new_left = l;
            /*********************/


            /*********************/
            l = up; r = down;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (target >= matrix[mid + 1][new_left])
                    l = mid + 1;
                else
                    r = mid;
            }
            new_down = l;
            /*********************/

            /*********************/
            l = up; r = down;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (target <= matrix[mid][new_right])
                    r = mid;
                else
                    l = mid + 1;
            }
            new_up = l;
            /*********************/

            if (left == new_left && right == new_right && up == new_up && down == new_down)
                return true;

            up = new_up;
            down = new_down;
            left = new_left;
            right = new_right;

        }
        return matrix[up][left] == target;
    }
};

算法2

(单调性扫描) $O(n + m)$

1. 初始化 up = 0，right = n - 1，从右上角元素开始。
2. 如果发现 matrix[up][right] == target，则直接返回 true；
3. 若 matrix[up][right] < target，则向下移动 up++；
4. 否则，向左移动 right--；
5. 如果出界返回 false。

时间复杂度

• 可以看到每次 up 向下移动或者 right 向左移动，移动次数不超过 $n+m$ 次，故时间复杂度为 $O(n+m)$。

C++ 代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0)
            return false;

        int n = matrix[0].size();

        int up = 0, right = n - 1;
        while (up < m && right >= 0) {
            if (matrix[up][right] == target)
                return true;
            else if (matrix[up][right] < target)
                up++;
            else
                right--;
        }

        return false;
    }
};