题干

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大

用例

例如对于下面矩阵：

[
    [1,   3,  5,  9],
    [10, 11, 12, 30],
    [230, 300, 350, 500]
]

要搜索的目标值为3，返回true；
示例1
输入：

[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3

返回值：

true

解答

有效信息：

• 每一行的数字都从左到右递增
• 每一行的第一个数字都比上一行最后一个数字大

故此此矩阵有序，可用二分查找取值。

方法一：两次二分查找

可以先通过二分查找确定 行，再对该 行 继续进行二分查找 ，常规思维：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度：
O ( log ⁡ m + log ⁡ n ) = O ( log ⁡ m n ) O ( l o g m + l o g n ) = O ( l o g m n ) O(\log m+\log n)=O(\log mn)O(logm+logn)=O(logmn) O(logm+logn)=O(logmn)O(logm+logn)=O(logmn)
其中 mm 和 nn 分别是矩阵的行数和列数。

空间复杂度： O ( 1 ) O(1) O(1)。

方法二：一次二分查找

因为每一行的第一个数字都比上一行最后一个数字大 ，所以我们可通过 数学的方法 将其压缩为一个 一维矩阵

import java.util.*;
public class Solution {
    /**
     *
     * @param matrix int整型二维数组
     * @param target int整型
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        int M = matrix.length, N = matrix[0].length,left = 0, right = M * N - 1;
        while (left <= right) {
            int center = ( right - left) / 2 + left;
            int compute = matrix[center / N][center % N];
            if (compute < target) {
                left = center + 1;
            } else if (compute > target) {
                right = center - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度：O(logmn)，其中 m是矩阵的行 和 n 是矩阵的列
空间复杂度：O(1)，原有数组上进行操作，未申请额外空间