class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        '''
        Two binary searches, first across rows and then
        across columns to quickly find the target
        '''
        
        mid = -1
        start, end = 0, len(matrix) - 1
        
        # Figure out which row the number belongs to
        while start <= end:
            mid = (start + end) // 2
            
            if target > matrix[mid][-1]:
                start = mid + 1
            elif target < matrix[mid][0]:
                end = mid - 1
            else:
                break
                
        # If we never managed to find a row, that means number
        # doesn't exist
        if not start <= end:
            return False
        
        # The row to search
        row = matrix[mid]
        start, end = 0, len(row) - 1
        
        while start <= end:
            mid = (start + end) // 2
            
            if target == row[mid]:
                return True
            elif target > row[mid]:
                start = mid + 1
            else:
                end = mid - 1
        
        return False