搜索二维矩阵

理解题目：

题目给出了一个按照以下规则排列的 m x n 矩阵：

1. 每一行的整数从左到右按升序排列。

2. 每一行的第一个整数大于前一行的最后一个整数。

要求编写一个函数来确定矩阵中是否存在目标值。如果存在，返回 true；否则，返回 false。

代码实现：

public class SearchMatrix {
    // 搜索二维矩阵
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        int left = 0, right = m * n - 1;

        // 二分查找
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = matrix[mid / n][mid % n]; // 将一维索引转换为二维索引

            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

步骤解释：

1. 初始化左右边界为矩阵中元素的首尾索引，使用一维数组的索引来模拟二维数组。

2. 在循环中进行二分查找，直到左右边界相遇。

3. 在每次迭代中，计算中间索引的值，并将一维索引转换为二维索引。

4. 如果中间索引的值等于目标值，则返回 true。

5. 如果中间索引的值小于目标值，则将左边界向右移动一位，否则将右边界向左移动一位。

6. 循环结束后，如果没有找到目标值，则返回 false。

时间复杂度： 二分查找的时间复杂度为 O(log(mn))。

空间复杂度： 只使用了常数级别的额外空间，空间复杂度为 O(1)。