leetcode 74. Search a 2D Matrix

leetcode74.py

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        
        # find last num in first column that <= target
        lo = 0
        hi = m - 1
        while lo < hi:
            mid = lo + (hi - lo + 1) // 2
            if matrix[mid][0] <= target:
                lo = mid
            else:
                hi = mid - 1
        if matrix[lo][0] > target:
            return False
        
        row = lo
        
        # find target in that row
        lo = 0
        hi = n - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        
        return False