Search in row and column sorted 2D matrix.


  • 0
    H
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target, int i, int j, int m, int n) {
            
            if (i<0|| j<0 || i>n || j>m) return false;
            
            int ii = i + (n-i)/2;
            int jj = j + (m-j)/2;
    
            if (target == matrix[ii][jj])
                return true;
    
            else if (target < matrix[ii][jj])
            {
                return searchMatrix(matrix, target, i, j, m, ii-1) ||
                    searchMatrix(matrix, target, ii, j, jj-1, n);
            }
            else if (target > matrix[ii][jj])
            {
                return searchMatrix(matrix, target, ii+1, j, m, n) ||
                    searchMatrix(matrix, target, i, jj+1, m, ii);
            }
    
            return false;
        }
        
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            
            if (matrix.size()==0) return false;
            
            return searchMatrix(matrix, target, 0, 0, matrix[0].size()-1, matrix.size()-1); 
            
        }
    };
    

Log in to reply
 

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