public class Solution {
    public boolean Find(int target, int [][] array) {
        if (0 == array.length) {
            return false;
        }
        if (1 == array.length) {
            if (0 == array[0].length) {
                return false;
            }
            return array[0][0] == target ? true : false;
        }
        // 具体代码实现
        // 思路:假设这个二维数组是一个方阵,我们只需要沿着对角线找就好了
        /*
         * 如果对角线上的某个值小于target,那么就以该位置为起点,向左画一条线,向上画一条线,然后,这一部分的值的大小一定也是小于target值的。(看不懂这段话,就自己作个图,不难的)
         * 如果对角线上的某个值等于target,那么很好,直接返回true即可。
         * 如果对角线上的某个值大于target,那么就以当前位置为起点,向右画一条线,向下画一条线,然后,这两条线围成的部分就不需要再进行查找了。同时,我们一共划分出了四个区域。然后使用递归,对另外没被直线围起来的两个区域进行查找,最终返回结果。
         * 强调一下,我们假设了这个二维数组是一个方阵。非方阵的做法有一丢丢不同。
         */
        // 定义一个整型变量,用于临时存放数据
        int tmp = 0;
        // 定义一个计数器
        int acc = 0;
        
        /******************************************************************************************************/
        // 我就知道,题目没有说明,那二维数组就不一定是方阵(最后一组用例错了,报了数组越界)
        // 定义一个整型变量,用于存放二维数组一维的长度
        int il = array.length;
        // 定义一个整型变量,用于存放二维数组二维的长度
        int jl = array[0].length;
        
        // 如果是方阵,才使用下列方法
        if (il == jl) {
            // 说明一下,i 是横坐标,j 是纵坐标
            for (int i = 0, j = 0; i < il && j < jl; i++, j++) {
                tmp = array[i][j];
                if (tmp == target) {
                    // 如果等于目标值,爽歪歪,直接返回
                    return true;
                }
                else if (tmp < target) {
                    // 如果小于目标值,继续沿着对角线向右下方向进行移动
                }
                else {
                    // 如果大于目标值,那么就以当前位置为起点,向右画一条线,向下画一条线,然后,这两条线围成的部分就不需要再进行查找了。同时,我们一共划分出了四个区域。然后使用递归,对另外没被直线围起来的两个区域进行查找,最终返回结果。
                    // 好吧,递归失败了,主要是我不知道怎么用Java切割一个二维数组。那么我们换个思路,计数器的作用就是,后续的遍历,不需要一直遍历到(i, j)这个位置,只需要在(i - k, j - k)位置即可
                    for (int k = 0; k < i - acc; k++) {
                        tmp = array[i][k]; // 从左往右
                        if (tmp == target) {
                            return true;
                        }
                        tmp = array[k][j]; // 从上往下
                        if (tmp == target) {
                            return true;
                        }
                    }
                    acc++;
                }
            }
            return false;
        }
        else { // 如果是非方阵
            // 下面代码是看了某个大佬才写出来的
            // 定义两个指针
            int ip = 0;
            int jp = jl - 1;
            while (ip < il && jp >= 0) {
                tmp = array[ip][jp];
                if (tmp == target) {
                    return true;
                }
                else if (tmp < target) {
                    ip++;
                }
                else {
                    jp--;
                }
            }
            return false;
        }
    }
}