leetcode74 搜索二维矩阵

思路

可以使用二叉搜索，首先先看标准的闭区间二叉搜索代码

public int qSearch(int[] a,int l,int r,int target){
    int mid=(l+r)/2;
    if(l>r) return l;//终止条件，区间为空
    if(a[mid]==target) return mid;
    else if(a[mid]<target) return qSearch(a,mid+1,r,target);
    else return qSearch(a,l,mid-1,target);
}

这里l>r时返回的是l，可以举例来看，a=[1,2,3,5,6],target=4

1.l=0,r=4,mid=2,a[mid]=3<4 =>

2.l=mid+1=3,r=4,mid=3,a[mid]=5>4 =>

3.l=3,r=2,mid=2此时区间长度为负，return l那就是返回大的一边也就是3，适用于插入的情况

反之如果第三行改成if(l>r) return r 那就是返回小的一边，那就是2，适用于搜索二叉矩阵

这道题的话，可以对行进行二叉搜索，找到可能出现target的行，然后遍历

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int ans=searchRow(matrix,0,matrix.length-1,target);
        if(ans==-1||ans>=matrix.length) return false;
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[ans][i]==target) return true;
        }
        return false;
    }
    public int searchRow(int[][] matrix,int l,int r,int target){
        int mid=l+(r-l)/2;
        if(l>r) return r;
        if(matrix[mid][0]==target) return mid;
        else if(matrix[mid][0]<target) return searchRow(matrix,mid+1,r,target);
        else return searchRow(matrix,l,mid-1,target);
    }
}