题目: 搜索二维矩阵

搜索二维矩阵

难度：中等

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 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⁴ <= matrix[i][j], target <= 10⁴

分析

方法一：暴力法

最直接的方法就是直接遍历整个矩阵，逐个比较目标值和矩阵中的元素。时间复杂度为 O(mn)。

代码示例（Java）：

public boolean searchMatrix(int[][] matrix, int target) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

方法二：二分查找

由于矩阵的每一行从左到右递增，每一列从上到下递增，可以将矩阵的左下角作为起点，比较左下角元素和目标值的大小，若目标值比左下角元素大，则往右查找，否则往上查找。时间复杂度为 O(m+n)。

代码示例（Java）：

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    int i = m - 1, j = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            i--;
        } else {
            j++;
        }
    }
    return false;
}

方法三：二分查找

由于矩阵的每一行和每一列都是递增的，可以将矩阵看作是一个一维的有序数组。可以将二维矩阵的坐标转换成一维数组的下标，然后使用二分查找算法来查找目标值。时间复杂度为 O(log(mn))。

代码示例（Java）：

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    int left = 0, right = m * n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int midVal = matrix[mid / n][mid % n];
        if (midVal == target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}