leetcode热题HOT 240. 搜索二维矩阵 II

一、问题描述：

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

二、二叉搜索树

1. 解题思路：利用矩阵每行和每列元素有序的特点，从右上角开始查找。这样可以利用行和列的有序性逐步缩小搜索范围。类似于二叉搜索树中左子树的值均小于根节点，右子树的值大于根节点的规律。
   如果目标值比当前元素大，则向下移动一行；如果目标值比当前元素小，则向左移动一列；直到找到目标值或者超出矩阵范围。

2. 具体步骤：
   ① 初始化起始位置为右上角（i=0，j=matrix[0].length-1）。
   ② 在矩阵范围内循环搜索，直到找到目标值或者搜索范围为空。
   ③ 比较目标值与当前元素的大小：
   （1）如果目标值大于当前元素，向下移动一行（i++）。
   （2）如果目标值小于当前元素，向左移动一列（j–）。
   （3）如果目标值等于当前元素，返回 true 表示找到目标值。
   ④ 如果未找到目标值，则返回 false。

3. 代码示例

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1; // 初始化起始位置为右上角
        while (i < matrix.length && j >= 0) { // 在矩阵范围内循环搜索
            if (target > matrix[i][j]) { // 如果目标值大于当前值，向下移动
                i++;
            } else if (target < matrix[i][j]) { // 如果目标值小于当前值，向左移动
                j--;
            } else { // 找到目标值
                return true;
            }
        }
        return false; // 搜索范围为空，未找到目标值
    }
}

• 时间复杂度分析：最坏情况下，该算法在矩阵中进行线性搜索，时间复杂度为 O(m + n)，其中 m 是矩阵的行数，n 是矩阵的列数。
  空间复杂度：该算法只使用了常数级别的额外空间，因此空间复杂度也为 O(1)。

三、二分法查找

1. 解题思路：针对每一行进行二分搜索，以确定目标值在当前行的位置。
   如果目标值等于当前元素，则返回 true 表示找到目标值。
   如果目标值小于当前元素，则目标值可能在当前元素的左侧，向左继续二分搜索。
   如果目标值大于当前元素，则目标值可能在当前元素的右侧，向右继续二分搜索。

2. 具体步骤：
   ① 使用 for 循环遍历矩阵的每一行。
   ② 在当前行调用 search 函数进行二分搜索。
   ③ 在 search 函数中，使用指针 low 和 high 分别表示搜索范围的起始和结束位置。
   ④ 在 while 循环中进行二分搜索，直到 low 大于 high：
   （1）计算中间位置 mid，获取中间元素 num。
   （2）如果目标值等于中间元素 num，则返回 true 表示找到目标值。
   （3）如果目标值小于中间元素 num，则更新 high 为 mid - 1 继续在左侧搜索。
   （4）如果目标值大于中间元素 num，则更新 low 为 mid + 1 继续在右侧搜索。
   ⑤ 如果未找到目标值，则返回 false。

3. 代码示例

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) { // 遍历矩阵的每一行
            if (search(row, target)) { // 调用search函数在当前行中搜索目标值
                return true;
            }
        }
        return false;
    }
    public boolean search(int[] nums, int target) {
        int low = 0, high = nums.length - 1; // 初始化搜索范围
        while (low <= high) { // 二分搜索
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) { // 找到目标值
                return true;
            } else if (num > target) { // 目标值在左侧
                high = mid - 1;
            } else { // 目标值在右侧
                low = mid + 1;
            }
        }
        return false; // 没有找到目标值
    }
}

• 时间复杂度分析：矩阵有 m 行，每行有 n 个元素，搜索的时间复杂度为 O(mlogn)，其中 logn 是每行中的二分搜索时间复杂度。
  空间复杂度：该算法只使用了常数级别的额外空间，因此空间复杂度为 O(1)。

四、补充与总结：

在以上两种解题方法中，二分法查找和二叉搜索树的方式都是针对有序矩阵的搜索问题提出的高效算法。通过对矩阵特性的利用，我们可以避免对整个矩阵进行遍历搜索，从而降低时间复杂度。

• 二分法查找方法通过在每行进行二分搜索，将时间复杂度降低到了 O(mlogn)，其中 m 为行数，n 为列数。这种方法适用于每行元素有序排列的情况。
• 二叉搜索树的方法则利用了矩阵的特殊排列方式，从右上角开始搜索，通过逐行缩小搜索范围，最终找到目标值或者确定其不存在。该方法的时间复杂度为 O(m + n)，适用于每行和每列元素均有序排列的情况。