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

àì夳堔傛蜴生んèń 2023-10-06 19:04 21阅读 0赞

#### 目录 ####

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

## 1.题目 ##

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

**示例 1：**

![在这里插入图片描述][98f0cfcaa4424079b9afa95466de19bf.png]

输入：matrix = \[\[1,3,5,7\],\[10,11,16,20\],\[23,30,34,60\]\], target = 3  
输出：true

**示例 2：**

![在这里插入图片描述][15a3511479734c6b826fb9dcd574da8f.png]

输入：matrix = \[\[1,3,5,7\],\[10,11,16,20\],\[23,30,34,60\]\], target = 13  
输出：false

**提示：**  
m == matrix.length  
n == matrix\[i\].length  
1 <= m, n <= 100  
\-104 <= matrix\[i\]\[j\], target <= 104

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

## 2.思路 ##

（1）暴力搜索  
使用暴力搜索法，即直接遍历该矩阵，若矩阵中的某一元素值等于目标值 target，则直接返回 true，若矩阵中的某一元素值大于目标值 target 或者遍历结束后仍为找到，则返回 false；

（2）两次二分搜索  
由于每行中的整数从左到右按升序排列，并且每行的第一个整数大于前一行的最后一个整数，所以可知矩阵的第一列中的整数是从上到下按升序排列的。**故可以先对第一列使用依次二分搜索，即找出最后一个小于等于目标值 target 的元素，如果未找到，则直接返回 false，如果找到了，然后在该元素所在的行中使用第二次二分搜索，看目标值 target 是否存在**。

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

（4）Z 字形查找  
从 matrix\[i\]\[j\] 为起点开始查找，其中 i = 0，j = n - 1：

*  如果 matrix\[i\]\[j\] == target，则直接返回 true；
 *  如果 matrix\[i\]\[j\] < target，则 i++；
 *  如果 matrix\[i\]\[j\] > target，则 j–；

遍历结束后，如果还未找到 target，则返回 false。

相关题目：  
[LeetCode\_二分搜索\_中等\_240.搜索二维矩阵 II][LeetCode_240._ II]

## 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;
    	            }
    	            if (matrix[i][j] > target) {
        
    	                return false;
    	            }
    	        }
    	    }
    	    return false;
    	}
    }

//思路2————两次二分搜索
    class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            int left = -1, right = m - 1;
            //第一次二分搜索，在第一列中找出最后一个小于等于目标值 target 的元素
            while (left < right) {
        
                int mid = (right - left + 1) / 2 + left;
                if (matrix[mid][0] == target) {
        
                    return true;
                } else if (matrix[mid][0] > target) {
        
                    right = mid - 1;
                } else {
        
                    left = mid;
                }
            }
            if (left < 0) {
        
                //未找到最后一个小于等于目标值 target 的元素
                return false;
            } else {
        
                //第二次二分搜索
                int row = left;
                left = 0;
                right = n - 1;
                while (left <= right) {
        
                    int mid = (right - left) / 2 + left;
                    if (matrix[row][mid] == target) {
        
                        return true;
                    } else if (matrix[row][mid] > target) {
        
                        right = mid - 1;
                    } else {
        
                        left = mid + 1;
                    }
                }
                return false;
            }
        }
    }

//思路3————一次二分搜索
    class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            int low = 0;
            int high = m * n - 1;
            while (low <= high) {
        
                int mid = low + (high - low) / 2;
                int x = matrix[mid / n][mid % n];
                if (x == target) {
        
                    return true;
                } else if (x < target) {
        
                    low = mid + 1;
                } else {
        
                    high = mid - 1;
                }
            }
    	    return false;
        }
    }

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

[98f0cfcaa4424079b9afa95466de19bf.png]: https://img-blog.csdnimg.cn/98f0cfcaa4424079b9afa95466de19bf.png
[15a3511479734c6b826fb9dcd574da8f.png]: https://img-blog.csdnimg.cn/15a3511479734c6b826fb9dcd574da8f.png
[LeetCode_240._ II]: https://blog.csdn.net/weixin_43004044/article/details/124920766