74. 搜索二維矩陣

給你一個滿足下述兩條屬性的 m x n 整數矩陣：

  • 每行中的整數從左到右按非嚴格遞增順序排列。
  • 每行的第一個整數大於前一行的最後一個整數。

給你一個整數 target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

 

示例 1：

74. 搜索二維矩陣_搜索

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true

示例 2：

74. 搜索二維矩陣_Math_02

輸入：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
  • -104 <= matrix[i][j], target <= 104


class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (target<matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]) {
            return false;
        }
        int rowNum = findRow(matrix, target);
        int[] row = matrix[rowNum];
        int left = 0, right = row.length-1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == row[mid]) {
                return true;
            }
            if (target < row[mid]) {
                right = mid-1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

    private int findRow(int[][] matrix, int target) {
        int left = 0, right = matrix.length-1;
        while (left <= right) {
            int mid = (left + right) /2;
            if (target == matrix[mid][0]) {
                return mid;
            }
            if (target < matrix[mid][0]) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return Math.min(left, right);
    }
}