给你一个满足下述两条属性的 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

解题思路

两次二分：

• 第一次查找每一列的第一个元素， 即 matrix[m][0] ，找到是哪一行
• 第二次查找命中的那一行 ，即 matrix[match][i]

注意点：

• 第一次查找如果没有直接命中 target ，那么 left - 1 就是要找的那一行， 注意越界问题

target =  11
int[][] matrix = new int[][]{
        {1,3,5,7},
        {10,11,16,20},
        {23,30,34,60}
};

Java 实现

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        int right = matrix.length - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (target > matrix[mid][0] ){
                left = mid + 1;
            } else if (target < matrix[mid][0]){
                right = mid - 1;
            } else {
                return true;
            }
        }
        // 注意越界，如果找到的是第一行，那么是 0 ，否则是 left - 1
        int match = left == 0 ? 0 : left - 1;
        left = 0;
        right = matrix[match].length - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (target > matrix[match][mid]){
                left = mid + 1;
            } else if (target < matrix[match][mid]){
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}