def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols
    while left < right:
        mid = (left + right) // 2
        r, c = divmod(mid, cols)
        value = matrix[r][c]
        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid
    return False