LeetCode_二分搜索_中等_240.搜索二维矩阵 II

快来打我* 2023-10-06 22:45 173阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：  
每行的元素从左到右升序排列。  
每列的元素从上到下升序排列。

**示例 1：**  
![在这里插入图片描述][af085fc26dc34efe98b353a02e533acc.png]  
输入：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：**  
![在这里插入图片描述][edef2afa520445a6a5f465a1fe17a3e6.png]  
输入：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  
\-109 <= matrix\[i\]\[j\] <= 109  
每行的所有元素从左到右升序排列  
每列的所有元素从上到下升序排列  
\-109 <= target <= 109

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

## 2.思路 ##

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

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

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

相关题目：  
[LeetCode\_二分搜索\_中等\_74.搜索二维矩阵][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;
        }
    }

[af085fc26dc34efe98b353a02e533acc.png]: https://img-blog.csdnimg.cn/af085fc26dc34efe98b353a02e533acc.png
[edef2afa520445a6a5f465a1fe17a3e6.png]: https://img-blog.csdnimg.cn/edef2afa520445a6a5f465a1fe17a3e6.png
[Link 1]: https://leetcode.cn/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/
[LeetCode_74.]: https://blog.csdn.net/weixin_43004044/article/details/119923477