class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Get the number of rows (m) and columns (n) in the matrix
        m = len(matrix)
        n = len(matrix[0])

        # Initialize two pointers: left and right
        left = 0
        right = m * n - 1

        # Perform binary search on the flattened matrix
        while left <= right:
            # Calculate the middle index
            mid = (left + right) // 2

            # Convert the middle index to row and column indices
            row = mid // n
            col = mid % n

            # Get the middle element
            mid_element = matrix[row][col]

            # If the middle element is equal to the target, return True
            if mid_element == target:
                return True

            # If the middle element is greater than the target,
            # search the left half of the matrix
            if mid_element > target:
                right = mid - 1
            # If the middle element is less than the target,
            # search the right half of the matrix
            else:
                left = mid + 1

        # If the target is not found, return False
        return False