剑指Offer04.二维数组中的查找(BST)

原题链接

思路：这题乍看上去好像是一个二分，其实上有更优的解法，由于从右上角往左下角看刚好是一颗二叉搜索树的形状，因此可以把这个二维数组看作是一个BST，因此解法就是BST的查找功能在此数组中的实现，将右上角元素看为根节点，从根节点开始，如果当前元素小于目标元素则找他的左子树，大于则找他右子树，否则就说明找到了，如果一直到数组越界都没有找到说明BST中不存在这个数。

参考代码

public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int maxY = matrix.length;
        int maxX = 0;
        if(maxY > 0) {
            maxX = matrix[0].length;
        }
        boolean flag = false;
        int x = maxX - 1, y = 0;
        while(x >= 0 && y < maxY) {
            if(matrix[y][x] > target) {
                x --;
            } else if(matrix[y][x] < target) {
                y ++;
            } else {
                flag = true;
                break;
            }
        }
        return flag;
    }