[Python] Implementation Example for Search a 2D Matrix II- Using D&C method
Tung Anh
220
exploreRecursion II

I cannot go to Solution part of the exercise, so I posted my code here for recommendation to improve my running time. Infact, running time is relatively slow with my algorithm. This is just an example for me to learn D&C.
"""

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = len(matrix)
        # Base case
        if(row == 0): return False
        col = len(matrix[0])
        if(col == 0): return False
        if (row == 1 and col == 1):
            if (matrix[0][0] ==  target):
                return True
            else:
                return False
        # Divide and conquer
        if(col%2==0):
            pivot = int(col/2) - 1
        else:
            pivot = int(col/2)
        for i in range (0, row):
            if(matrix[i][pivot] == target):
                return True
            elif (matrix[i][pivot] > target):
                top_right = [matrix[j][pivot+1:] for j in range(0, i)]
                bottom_left = [matrix[j][:(pivot)] for j in range(i, row)]
                bottom_left_result = self.searchMatrix(bottom_left, target)
                top_right_result = self.searchMatrix(top_right, target)
                return (bottom_left_result or top_right_result)
        right = [matrix[i][pivot+1:] for i in range(0, row)]
        return self.searchMatrix(right, target)

"""

Comments (1)