240.搜索二维矩阵 Ⅱ

题目：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

题解：

方法一：遍历整个二维数组，如果找到target返回true，如果没找到就返回false，由于这道题二维数组的长和宽最大是300，所以最大数据量是90000，不是很大，所以遍历这种暴力方法也能accept。但是不推荐用这种方法，没有什么算法可言。

public boolean searchMatrix_bl(int[][] matrix, int target) {
    int m = matrix.length,n = matrix[0].length;
    for (int i = 0;i<m;i++){
        for (int j = 0;j<n;j++){
            if (matrix[i][j]==target)
                return true;
        }
    }
    return false;
}

方法二： 二分查找，但是这道题和搜索二维数组Ⅰ不一样的地方是，这道题的数组并不保证第二行都大于第一行，所以没办法用两次二分的方式，需要对每一行/列进行二分，如果找到了就返回true，如果遍历了所有行/列都没找到，那么就返回false。

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length,n = matrix[0].length;
    for (int i = 0;i<m;i++){
        int l = 0, r = n-1;
        while(l<r){
            int mid = (l+r+1)>>1;
            if (matrix[i][mid]<=target) l = mid;
            else r = mid-1;
        }
        if (matrix[i][r]==target) return true;
    }
    return false;
}

方法三： 参考宫水三叶大佬的方法，可以把这个二维数组看成搜索二叉树（BST），右上角作为根节点，同行的作为左子树，同列的作为右子树，这样正好符合了搜索二叉树的定义，左子树上的节点都比根节点小，右子树上的节点都比根节点大。之后从右上角开始查找，如果当前节点的值比target大，就往左找，列数c–，如果当前节点的值比target小，就往下找，行数r++，如果超出了二维数组的范围还没找到，就是没有，就返回false

public boolean searchMatrix_BST(int[][] matrix, int target) {
    int m = matrix.length,n = matrix[0].length;
    int r = 0,c = n-1;
    while(r<m&&c>=0){
        if (matrix[r][c]<target) r++;
        else if (matrix[r][c]>target) c--;
        else return true;
    }
    return false;
}