leetcode Question 92: Search a 2D matrix

Search a 2D matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [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]
]

Given target = 5, return true.

Given target = 20, return false.

Analysis:

First glance at this problem easily reminds us the classic search algorithm: binary search. But this time it is required to search if the "target" value exists in the 2D matrix rather than 1D array.

A good start point is to consider the 1D binary search, every time we choose the middle element and compare to the target value, then recursively search the related subset until found or finished.

What about 2D sorted matrix?  Let's see the matrix below:
  [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]

Since it is sorted both row-wise and column-wise, for any sub matrix, the smallest element must be the top-left element, and the largest one must be on the right bottom. 

Now, it seems that the diagonal should be the mid-element similar to the 1D binary search. But how shall we divide the matrix into sub matrices? Let's see the matrix below:

  [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]

The whole matrix is divided into 4 sub matrices (blue, green, yellow, and red in the above matrix), by diagonal element 9.  So it is not hard to get the following properties:
(1) elements in blue < 9
(2) elements in red > 9
(3) elements in yellow and green, we don't know.

So, given a target value t, we could first compare the value to the mid element in the current matrix, then search either (blue, green and yellow) or (red, green and yellow) sub matrices, according to the value comparison. Then a simple recursion can be done for the whole searching process, which is same as the classic binary search.

Code(C++):

class Solution {
public:
    bool search(vector > &matrix, int &target, int st_r, int ed_r, int st_c, int ed_c){
        if (st_r > ed_r || st_c > ed_c || matrix[st_r][st_c] > target || matrix[ed_r][ed_c]< target) {return false;}
        int mid_r = st_r + (ed_r-st_r)/2;
        int mid_c = st_c + (ed_c-st_c)/2;
        
        if (matrix[mid_r][mid_c] == target){
            return true;
        }else if (matrix[mid_r][mid_c] > target) {
            return (search(matrix, target, st_r, mid_r, st_c, mid_c) ||
                    search(matrix, target, st_r,mid_r, mid_c+1, ed_c)||
                    search(matrix, target, mid_r+1, ed_r, st_c, mid_c));
        }else{
            return (search(matrix, target, mid_r+1, ed_r, mid_c+1, ed_c) ||
                    search(matrix, target, st_r,mid_r, mid_c+1, ed_c)||
                    search(matrix, target, mid_r+1, ed_r, st_c, mid_c));
        }
    }

    bool searchMatrix(vector>& matrix, int target) {
        int sz_row = matrix.size();
        if (sz_row == 0) { return false; }
        int sz_col = matrix[0].size();
        
        return search(matrix, target, 0, sz_row-1, 0, sz_col-1);
    }
};

Code(Python):

class Solution(object):
    def search(self, matrix, target, st_r, ed_r, st_c, ed_c):
        if st_r > ed_r or st_c > ed_c or matrix[st_r][st_c] > target or matrix[ed_r][ed_c]< target:
            return False
            
        mid_r = st_r + (ed_r-st_r)/2
        mid_c = st_c + (ed_c-st_c)/2
        
        if matrix[mid_r][mid_c] == target:
           return True
           
        elif matrix[mid_r][mid_c] > target:
            return self.search(matrix, target, st_r, mid_r, st_c, mid_c) or \
                   self.search(matrix, target, st_r,mid_r, mid_c+1, ed_c) or \
                   self.search(matrix, target, mid_r+1, ed_r, st_c, mid_c)
        else:
            return self.search(matrix, target, mid_r+1, ed_r, mid_c+1, ed_c) or \
                   self.search(matrix, target, st_r,mid_r, mid_c+1, ed_c) or \
                   self.search(matrix, target, mid_r+1, ed_r, st_c, mid_c)
    
    
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        sz_r = len(matrix)
        if sz_r == 0:
            return False
        sz_c = len(matrix[0])
        
        return self.search(matrix, target, 0, sz_r-1, 0, sz_c-1)