力扣240.搜索二维矩阵II

法1：

我们可以从右上角开始查找，若当前值大于待搜索值，我们向左移动一位；若当前值小于待搜索值，我们向下移动一位。如果最终移动到左下角时仍不等于待搜

索值，则说明待搜索值不存在于矩阵中。

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

法2：二分搜索

沿着对角线遍历，对每个对角线元素所在的行、列分别进行二分搜索。

class Solution {
    public boolean bianrySearch(int[][] matrix,int target,int start,boolean vertical){
        int lo = start;
        int hi = vertical?matrix[0].length-1:matrix.length-1;
        while(hi>=lo){
            int mid = (lo+hi)/2;
            if(vertical){
                if(matrix[start][mid] < target)
                    lo = mid + 1;
                else if(matrix[start][mid] > target)
                    hi = mid - 1;
                else
                    return true;
            }else{
                if(matrix[mid][start] < target)
                    lo = mid + 1;
                else if(matrix[mid][start] > target)
                    hi = mid - 1;
                else
                    return true;
            }
        }
        return false;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0)
            return false;
        int shorterDim = Math.min(matrix[0].length,matrix.length);
        for(int i = 0;i<shorterDim;i++){
            boolean verticalFound = bianrySearch(matrix,target,i,true);
            boolean horizontalFound = bianrySearch(matrix,target,i,false);
            if(verticalFound||horizontalFound)
                return true;
        } 
        return false;
    }
}