Binary search on rows and columns separately


  • 0
    S
    public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix.length == 0 || matrix[0].length == 0){
                return false;
            }
            
            int m = matrix.length, n = matrix[0].length;
            
            int rmin = 0, rmax=m-1;
            //binary search to find r
            while(rmin < rmax){
                int r = rmin + (rmax - rmin)/2;
                if(matrix[r][n-1] == target){
                    return true;
                }else if(matrix[r][n-1] < target){
                    rmin = r + 1;
                }else{
                    rmax = r;
                }
            }
            
            //target is in row rmin
            //binary search to find c
            int cmin = 0, cmax = n - 1;
            while(cmin <= cmax){
                int c = cmin + (cmax - cmin)/2;
                if(matrix[rmin][c] == target){
                    return true;
                }else if(matrix[rmin][c] > target){
                    cmax = c - 1;
                }else{
                    cmin = c + 1;
                }
            }
            
            
            return false;
            
        }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.