Legally, this isn't necessarily the case.
The border search exception says that proximity to a border is inherently justification to search people without a warrant or probable cause, so the position of the Supreme Court is that agents don't have the normal burden of evidence for such actions. US v. Martinez-Fuerte went further and held that drivers can be directed to secondary screening without even reasonable suspicion.
The article is accurate but misleading when it discusses the conditions for these searches. (For instance, "calls into question whether the man, who is Muslim, was singled out because of his faith", "the border search exception is grounded in traversal of the border itself".) It's true that this raises questions about whether profiling was used, but the implicit "which is illegal" is false: the border search caselaw explicitly permits otherwise-illegal ethnic profiling. And "grounded in traversal" does not mean "pursuant to evidence of traversal": once again, Martinez suggests that searches to check whether someone has crossed are legal. Even "accumulated occupational biases" are a search rationale as 'training' and 'professional experience'.
There are a number of reasons this search still appears illegal, and the counsels interviewed for the story are understandably dubious But the boundaries of what's legal here extend well past what I find horrifying: searching people at the border without proof, explicitly on the basis of institutional opinions and racial profiling, has been upheld as legal.