Are you a lawyer? I’m not, but the Legal Eagle video linked elsewhere in this thread says that the reasons for the search are the crux of the “lawful” part, not the location.

(The location was at the port of entry—the border—which is pretty much the definition of the CBP’s jurisdiction.)