一、题目

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

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

示例 1：

输入：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

示例 2：

输入：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 = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析及代码

1. 从左下或右上搜索/Z字形查找

（1）思路

若按下标从左上角搜索，由于向下、向右数值均单调递增，导致无法准确判断搜索方向；

若从左下角搜索，则可以准确判断搜索方向：

当前值 > target，搜索上方数值；
当前值 < target，搜索右方数值；

可以不断迭代，直至搜索到目标 target （true）或超出矩阵范围（false）。

（2）代码（C++）

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i = matrix.size() - 1, j = 0;
        while (i > -1 && j < matrix[0].size()) {
            if (matrix[i][j] > target)
                i--;
            else if (matrix[i][j] < target)
                j++;
            else   
                return true;
        }
        return false;
    }
};

（3）结果（C++）

执行用时：64 ms, 在所有 C++ 提交中击败了 94.18% 的用户；
内存消耗：12.6 MB, 在所有 C++ 提交中击败了 95.57% 的用户。

Java_63">（4）代码（Java）

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = m - 1, j = 0;//搜索指针的行、列坐标
        while (i >= 0 && j < n) {//指针在矩阵范围内时
            if (matrix[i][j] == target) {//找到目标值
                return true;
            } else if (matrix[i][j] < target) {//当前元素小于目标值，增大列坐标
                j++;
            } else {//当前元素大于目标值，减小行坐标
                i--;
            }
        }
        return false;//搜索完成后未在矩阵中发现目标值
    }
}

Java_82">（5）结果（Java）

执行用时：5 ms，在所有 Java 提交中击败了 96.28% 的用户；
内存消耗：44 MB，在所有 Java 提交中击败了 39.76% 的用户。

2. 二分搜索

（1）思路

先在矩阵的 45 度对角线上二分搜索，直至发现 target（返回true）或找到 matrix[i][i] < target < matrix[i + 1][i + 1]。

将此时的矩形划分为 4 块讨论，左上部分的数值全部小于 target，右下部分的数值全部大于 target，可跳过。

针对左下部分和右上部分的矩阵进一步二分迭代，直至发现 target。

（2）代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty())
            return false;
        return search(matrix, target, 0, 0, matrix.size(), matrix[0].size());
    }

    bool search(vector<vector<int>>& matrix, int target, int li, int lj, int ri, int rj) {//参数为所搜索矩阵的左下、右上坐标
        if ((li > ri - 1) || (lj > rj - 1) || matrix[li][lj] > target || matrix[ri - 1][rj - 1] < target)
            return false;
        int li0 = li, lj0 = lj, ri0 = ri, rj0 = rj;     
        while (li < ri - 1 || lj < rj - 1) {//二分搜索对角线
            int mi = (li + ri) / 2, mj = (lj + rj) / 2;
            if (matrix[mi][mj] > target) {
                ri = mi;
                rj = mj;
            }
            else {
                li = mi;
                lj = mj;
            }
        }
        if (matrix[li][lj] == target)
            return true;
        return search(matrix, target, li + 1, lj0, ri0, lj + 1) || search(matrix, target, li0, lj + 1, li + 1, rj0);//递归搜索左下和右上矩阵
    }
};