human
I am working on the file "02_BinarySearch.ipynb".
The first task is:
Search a 2D Matrix
Write an efficient algorithm with O(m + n) 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.
Can you write Python code for it?
 ... What is a the Python code you requested?
assistant
#Here is the Python code you requested.

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or len(matrix) == 0:
            return False
        if len(matrix[0]) == 0:
            return False
        
        m, n = len(matrix), len(matrix[0])
        
        # O(m + n) brilliant
        r, c = 0, n-1
        while r <= m-1 and c >= 0:
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                c -= 1
            else:
                r += 1
        
        return False
        
        
        # O(mlogn), straight forward
        for i in range(m):
            if matrix[i][0] <= target <= matrix[i][-1]:
                start, end = 0, n-1
                while start + 1 < end:
                    mid = start + (end - start) / 2
                    if matrix[i][mid] == target:
                        return True
                    elif matrix[i][mid] < target:
                        start  = mid + 1
                    else:
                        end = mid - 1
                if matrix[i][start] == target or matrix[i][end] == target:
                    return True
        return False