https://leetcode.com/problems/search-a-2d-matrix-ii/description/

search-a-2d-matrix-ii.py

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        def search( tl, br ):
            print 'Searching...'
            print tl, br
            if tl[0] > br[0] or tl[1] > br[1]: return False
            if tl == br: return target == matrix[tl[0]][tl[1]]
            
            x = (tl[0]+br[0])/2
            y = (tl[1]+br[1])/2
            print 'Checking...'
            print x, y
            if matrix[x][y] == target:
                return True
            if matrix[x][y] < target:
                found_in_bottom_left = search( (x+1, tl[1]), (br[0], y) )
                if found_in_bottom_left: return True
                found_in_right = search( (tl[0], y+1), br )
                if found_in_right: return True
                return False
            if target < matrix[x][y]:
                found_in_top_right = search( (tl[0], y), (x-1, br[1]) )
                if found_in_top_right: return True
                found_in_left = search( tl, (br[0], y-1) )
                if found_in_left: return True
                return False
            
                
            
        if not matrix:
            return False
        return search( (0,0), (len(matrix)-1, len(matrix[0])-1) )