public class Solution {
    public boolean Find(int target, int [][] array) {
        //方法一：遍历二维数组，时间复杂度：O(m*n)
//        int len1 = array.length;
//        //特殊值处理，空数组不可能存在目标值
//        if(len1 == 0){
//            return false;
//        }
//        int len2 = array[0].length;
//        //二层循环遍历二维数组
//        for(int i=0;i<len1;i++){
//            for (int j=0;j<len2;j++){
//                if(array[i][j] == target){
//                    return true;  //如果存在目标值，则返回true
//                }
//            }
//        }
//        return false;

        //方法二：遍历二维数组，对方法一优化
//        int len1 = array.length;
//        //特殊值处理，空数组不可能存在目标值
//        if(len1 == 0){
//            return false;
//        }
//        int len2 = array[0].length;
//        //二层循环遍历二维数组
//        int lenY = len2;
//        for(int i=0;i<len1;i++){
//            for (int j=0;j<lenY;j++){
//                if(array[i][j] == target){
//                    return true;  //如果存在目标值，则返回true
//                }
//                if(array[i][j] > target){
//                    if(j < lenY){
//                        lenY = j;
//                    }
//                }
//                if(array[i][0] > target){
//                    return false;
//                }
//            }
//        }
//        return false;

        //方法三：利用二维行列递增特性，时间复杂度：O(m+n)
        int len1 = array.length;
        //特殊值处理，空数组不可能存在目标值
        if(len1 == 0){
            return false;
        }
        int len2 = array[0].length;
        int x = len1-1;  //最底行
        int y = 0;  //第一列
        while (x>=0 && x<len1 && y>=0 && y<len2){//如果数组越界，则不存在目标值
            if(array[x][y] == target){
                return true;
            }else if(array[x][y] < target){//如果目标值小于当前值，则目标值在右边，y++；
                y++;
            }else{//如果目标值大于当前值，则目标值在上边，x--；
                x--;
            }
        }
        return false;
    }
}