74.搜索二维矩阵

题目:74.搜索二维矩阵

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

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

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

• 示例 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

• 提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

思路

1. 矩阵视为一维数组：由于矩阵的特殊排序性质，可以将矩阵拉平成一个排序的一维数组。第 i 行和第 j 列的元素在一维数组中的索引 index 为 i * n + j，其中 n 是矩阵的列数。同样一维数组中的索引 index 对应的矩阵元素为 matrix[index / n][index % n]。

2. 计算中间索引：中间索引 mid = left + (right - left) / 2。通过 matrix[mid / n][mid % n] 来找到中间索引对应的矩阵元素。

3. 二分查找：使用二分查找来搜索这个“虚拟”的一维数组，查找目标值。

• 时间复杂度:O(log₂mn)
• 空间复杂度:O(1)

代码

public boolean searchMatrix(int[][] matrix, int target) {
    // 矩阵的行数
    int m = matrix.length;
    // 矩阵的列数
    int n = matrix[0].length;
    int left = 0;
    // 将矩阵视为长度为 m * n 的一维数组
    int right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 计算出中间值在矩阵中的位置
        int midValue = matrix[mid / n][mid % n];
        if (target == midValue) {
            return true;
        } else if (target > midValue) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}