074._search_a_2d_matrix.md

###74. Search a 2D Matrix

题目: https://leetcode.com/problems/search-a-2d-matrix/

难度: Easy

二分Search

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False
        else:
            n = len(matrix[0])
            half = len(matrix)//2
            if  target >= matrix[half][0] and target <= matrix[half][n-1]:
                return self.searchList(matrix[half],target)
            elif target < matrix[half][0]:
                return self.searchMatrix(matrix[:half],target)
            else:
                return self.searchMatrix(matrix[half+1:],target)
        
    def searchList(self, lst, target):
        if len(lst) == 0:
            return False
        else:
            mid = len(lst) // 2
            if target == lst[mid]:
                return True
            elif target < lst[mid]:
                return self.searchList(lst[:mid],target)
            else:
                return self.searchList(lst[mid+1:],target)