74. 搜索二维矩阵

📝 题目描述

给你一个满足以下两个属性的 m x n 整数矩阵：

1. 每行的整数从左到右按非严格递增排列；
2. 每一行的第一个整数大于前一行的最后一个整数。

给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。

---

📌 示例

示例 1

输入：

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：

true

解释：target=3 位于矩阵第 1 行第 2 列。

示例 2

输入：

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：

false

---

🚀 最优解：二维转一维二分查找

🔍 思路解析

核心策略：把二维矩阵“拉直”成一维有序数组，用二分查找快速定位。 因为矩阵满足“每行递增、下一行首元素大于上一行尾元素”，所以整个矩阵等价于一个长度为 m*n 的一维有序数组。

1. 初始化二分边界：left=0（对应矩阵第1个元素），right=m*n-1（对应矩阵最后1个元素）；
2. 每次取中间索引 mid，将 mid 转换为矩阵的行列坐标：
   • 行号 = mid / 列数（mid // n）；
   • 列号 = mid % 列数（mid % n）；
3. 比较中间元素与 target：
   • 若中间元素 < target，说明 target 在右侧，更新 left=mid+1；
   • 若中间元素 > target，说明 target 在左侧，更新 right=mid-1；
   • 若相等，直接返回 true；
4. 遍历结束后仍未找到，返回 false。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取矩阵的行数和列数
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // 读取矩阵元素
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        // 读取目标值
        int target = scanner.nextInt();

        // 创建解决方案对象并计算结果
        Solution solution = new Solution();
        boolean result = solution.searchMatrix(matrix, target);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;    // 矩阵行数
        int n = matrix[0].length; // 矩阵列数
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 将mid转换为矩阵的行列坐标
            int row = mid / n;
            int col = mid % n;
            int midVal = matrix[row][col];

            if (midVal < target) {
                left = mid + 1;
            } else if (midVal > target) {
                right = mid - 1;
            } else {
                return true; // 找到目标
            }
        }
        return false; // 未找到
    }
}

---

🧠 通俗易懂解释

可以把矩阵想象成“一长串排好序的数”，比如示例1的矩阵等价于：[1,3,5,7,10,11,16,20,23,30,34,60]。 用二分法找target=3的过程：

1. 初始left=0，right=11，mid=5 → 对应矩阵第1行（5//4=1）第1列（5%4=1），元素是11，比3大，所以right=4；
2. 新mid=2 → 对应第0行（2//4=0）第2列（2%4=2），元素是5，比3大，所以right=1；
3. 新mid=0+1=0.5→0 → 对应第0行第0列，元素是1，比3小，所以left=1；
4. 新mid=1 → 对应第0行第1列，元素是3，等于target，返回true。

---

⏱ 时间复杂度

O(log(m*n))

二分查找的时间复杂度为对数级别，m*n是矩阵元素总数，效率远高于逐行遍历。

---

💾 空间复杂度

O(1)

仅使用left、right、mid等常数个变量，无额外空间消耗。

---

二分 int r = matrix.length * matrix[0].length - 1; / 和 % matrix[0].length 取得位置