Another easy-to-understand recursive solution with simple explanation !


  • 0
    A
     target = 21
    
      [                               
         [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]
       ]                             
      1. Search in the most right column   
      
      15
      19
      22-->start, top
      24
      30
    
      2. Search in the row [3,   6,   9,   16,   22]
                                            |
                                     startR, right
      3. Search in the sub matrix 
       [ 
         [3,  6,   9,  16],
         [10, 13,  14, 17],
         [18, 21,  23, 26]
       ]
    

    ""

    public boolean searchMatrix(int[][] matrix, int target) {
       int right = matrix[0].length-1;
       int top = 0;
        
          return findRecursive(matrix, target, right, top);
    }
    
    private boolean findRecursive(int[][] matrix, int target, int right, int top){
        if(top==matrix.length) return false;
        if(right<0) return false;
        
        int start = top;
        int end = matrix.length-1;
        //Search in the most right column
        while(start<=end){
            int mid = start + (end-start)/2;
            if(target == matrix[mid][right]) return true;
            else if(target < matrix[mid][right]) end = mid-1;
            else start = mid+1;
        }
        
        top = start;
        if(top==matrix.length) return false;
        
        int startR = 0;
        int endR = right;
        //Search in one row
        while(startR<=endR){
            int midR = startR + (end - start)/2;
            if(target == matrix[top][midR]) return true;
            else if(target < matrix[top][midR]) endR = midR - 1;
            else startR = midR+1;
        }
        
        return findRecursive(matrix, target, endR, top+1);
    }
    

    ""


Log in to reply
 

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