搜索二维矩阵——巧用右上角起点搜索法，高效解决二维矩阵查找问题

📖 问题描述

给定一个满足以下特性的 m x n 整数矩阵：

• 每行元素从左到右非严格递增

• 每行的第一个元素大于前一行的最后一个元素

要求判断目标值 target 是否存在于矩阵中。

示例 1：

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

示例 2：

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

🔍 算法解析

特性分析

该矩阵具有以下重要性质：

1. 行内有序：每行元素从左到右保持非递减

2. 行间严格递增：下一行的最小值 > 当前行的最大值

这意味着我们可以将这个二维矩阵展开视为一个严格递增的一维数组，直接使用二分搜索。但本文将介绍一种更直观的双指针法。

右上角起点搜索法

我们从矩阵的右上角（或左下角）开始搜索，利用矩阵特性缩小查找范围：

1. 起点选择：初始位置设为右上角元素 matrix[0][n-1]

2. 比较逻辑：

   • 若当前值 = target → 找到目标，返回true

   • 若当前值 < target → 排除当前行（向下移动）

   • 若当前值 > target → 排除当前列（向左移动）

这种策略每次操作都能排除一行或一列，将时间复杂度控制在 O(m+n)。

🖥 代码实现

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 处理空矩阵特例
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // 初始化指针到右上角
        int row = 0;
        int col = cols - 1;
        
        while (row < rows && col >= 0) {
            int current = matrix[row][col];
            if (current == target) {
                return true; // 找到目标值
            } else if (current < target) {
                row++; // 排除当前行，向下搜索
            } else {
                col--; // 排除当前列，向左搜索
            }
        }
        return false; // 搜索完毕未找到
    }
}

🧠 复杂度分析

• 时间复杂度：O(m + n)
  最坏情况下需要遍历所有行和列（例如从右上角到左下角）

• 空间复杂度：O(1)
  仅使用常数级别的额外空间

🌟 进阶思考

对于超大规模矩阵，可采用两次二分法优化：

1. 先对第一列二分查找确定目标行

2. 在目标行内进行二次二分查找

该方法可将时间复杂度优化至 O(log m + log n)，但代码实现相对复杂。读者可根据实际场景选择合适方法。

💡 应用场景

该算法模式适用于以下类型的二维搜索问题：

• 行内有序且行间有序的矩阵

• 需要快速判断元素存在的场景

• 内存有限，无法展开为一维数组的情况

掌握这种高效的搜索策略，能够帮助你在面试和竞赛中快速解决类似问题！