// @Title: 寻找目标值 - 二维数组 (寻找目标值 - 二维数组)
// @Author: qisiii
// @Date: 2022-02-06 23:04:14
// @Runtime: 0 ms
// @Memory: 47.4 MB
// @comment: 对角法寻找
// @flag: GREEN
class Solution {
       public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row<rows&&column>=0){
            if (target==matrix[row][column]){
                return true;
            }else if(target>matrix[row][column]){
                row++;
            }else {
                column--;
            }
        }
        return false;
    }
}

// @Title: 寻找目标值 - 二维数组 (寻找目标值 - 二维数组)
// @Author: qisiii
// @Date: 2022-02-06 22:54:21
// @Runtime: 0 ms
// @Memory: 47.5 MB
// @comment: 多次二分
// @flag: GREEN
class Solution {
    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int left=0;
            int right=matrix[i].length-1;
            while (left<=right){
                int middle=(left+right)/2;
                if (target==matrix[i][middle]){
                    return true;
                }else if(target>matrix[i][middle]){
                    left=middle+1;
                }else {
                    right=middle-1;
                }
            }
        }
        return false;
    }
}

// @Title: 寻找目标值 - 二维数组 (寻找目标值 - 二维数组)
// @Author: qisiii
// @Date: 2022-02-19 16:45:34
// @Runtime: 0 ms
// @Memory: 47.6 MB
// @comment: 
// @flag: 
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0){
            return false;
        }
        int row=0;
        int column=matrix[0].length-1;
        while(row<matrix.length&&column>=0){
            int current=matrix[row][column];
            if(current==target){
                return true;
            }else if (current>target){
                column--;
            }else{
                row++;
            }
        }
        return false;
    }
}