Leetcode 74. 搜索二维矩阵

快来打我* 2021-10-15 00:53 320阅读 0赞

### 文章目录 ###

*  1. 降维后二分查找
 *   *  1.1 思路
     *  1.2 复杂度
     *  1.3 代码
 *  2. 两次二分查找
 *   *  2.1 思路
     *  2.2 复杂度
     *  2.3 代码

# 1. 降维后二分查找 #

## 1.1 思路 ##

将二维数组转化为一维数组，仍能保持有序，再使用标准的二分查找。二维数组与一维数组的映射关系如下：

*  left = 0，right = m x n - 1；
 *  row = i / n，col = i % n。

## 1.2 复杂度 ##

时间复杂度：O(logmn)  
空间复杂度：O(1)

## 1.3 代码 ##

# 2. 两次二分查找 #

## 2.1 思路 ##

第一次对行进行二分查找，找出目标值所在行：

*  如果该行最小值大于 target，转到较小的半区；
 *  如果该行最大值小于 target，转到较大的半区；
 *  否则，target 位于当前行范围内；

第二次对特定列进行二分查找，找到目标值的具体位置。

## 2.2 复杂度 ##

时间复杂度：O(logm) + O(logn) = (logmn)  
空间复杂度：O(1)

## 2.3 代码 ##

class Solution { 
        public boolean searchMatrix(int[][] matrix, int target) { 
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 
                return false;
            }
    
            int m = matrix.length;
            int n = matrix[0].length;
            int left = 0;
            int right = m - 1;
            int mid = left + (right - left) / 2;
            while (left <= right) { 
                mid = left + (right - left) / 2;
                if (matrix[mid][0] > target) { 
                    right = mid - 1;
                } else if (matrix[mid][n - 1] < target) { 
                    left = mid + 1;
                } else { 
                    break;
                }
            }
            int row = mid;
            left = 0;
            right = n - 1;
            while (left <= right) { 
                mid = left + (right - left) / 2;
                if (matrix[row][mid] > target) { 
                    right = mid - 1;
                } else if (matrix[row][mid] < target) { 
                    left = mid + 1;
                } else { 
                    return true;
                }
            }
            return false;
        }
    }