1.题目

编写一个高效的算法来搜索 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⁹ <= matrix[i][j] <= 10⁹
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10⁹ <= target <= 10⁹

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-a-2d-matrix-ii

2.思路

（1）暴力穷举法
使用暴力搜索法，即直接遍历该矩阵，若矩阵中的某一元素值等于目标值 target，则直接返回 true，若矩阵中的某一元素值大于目标值 target，则说明当前行没有目标值 target，直接遍历下一行即可。若遍历结束后仍未找到 target，则返回 false。

（2）二分搜索
由于每行中的整数从左到右按升序排列，所以可以对矩阵中的每一行进行二分查找。

（3）Z 字形查找
思路参考本题官方题解。

相关题目：
LeetCode_二分搜索_中等_74.搜索二维矩阵

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
	public boolean searchMatrix(int[][] matrix, int target) {
	    int m = matrix.length;
	    int n = matrix[0].length;
	    for (int i = 0; i < m; i++) {
	        for (int j = 0; j < n; j++) {
	            if (matrix[i][j] == target) {
	                return true;
	            } else if (matrix[i][j] > target) {
	                /*
	                    每一行的元素从左到右是递增的
	                    如果 matrix[i][j] > target，则说明当前行没有目标元素 target，直接遍历下一行即可
	                */
	                break;
	            }
	        }
	    }
	    return false;
	}
}

//思路2————二分搜索
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        //对矩阵中的每一行进行二分查找
        for (int i = 0; i < m; i++) {
            //二分搜索，在第 i + 1 行中查找 target
            int left = 0;
            int right = n - 1; 
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (matrix[i][mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}

//思路3——Z 字形查找
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0;
        int y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            } else {
                ++x;
            }
        }
        return false;
    }
}