public class DayCode {    public static void main(String[] args) {        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};        int target = 3;        boolean ans = new DayCode().searchMatrix(matrix, target);        boolean ans1 = new DayCode().searchMatrix1(matrix, target);        System.out.println(ans);        System.out.println(ans1);    }
    /**     * 时间复杂度 O(log (m + n))     * 空间复杂度 O(1)     * @param matrix     * @param target     * @return     */    public boolean searchMatrix1(int[][] matrix, int target) {        int rowIdx = binarySearchFirstColumn(matrix, target);        if (rowIdx < 0) {            return false;        }        return binarySearchRow(matrix[rowIdx], target);    }
    private boolean binarySearchRow(int[] matrix, int target) {        int left = 0, right = matrix.length - 1;        while (left <= right) {            int mid = (right - left) / 2 + left;            if (matrix[mid] == target) {                return true;            } else if (matrix[mid] > target) {                right = mid - 1;            } else {                left = mid + 1;            }        }        return false;    }
    private 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;    }

    /**     * 时间复杂度 O (rows * cols)     * 空间复杂度 O (rows * cols)     * @param matrix     * @param target     * @return     */    public boolean searchMatrix(int[][] matrix, int target) {        Map<Integer, Integer> map = new HashMap<>();        for (int row = 0; row < matrix.length; row++) {            for (int col = 0; col < matrix[row].length; col++) {                map.put(matrix[row][col], matrix[row][col]);            }        }
        return map.containsKey(target);    }}