Firstly, because there isn't an explicit Constitutional "right to privacy", per se, and even if there was (and there are arguments that several constitutional provisions amount, in aggregate, to a right to privacy), that it wouldn't be absolute, in the same way that freedom of speech and of the press are not absolutes.
Indeed, the closest thing to a right to privacy, the 4th Amendment, has explicit caveats: "The right of the people to be secure in their persons, houses, papers, and effects, against unreasonable searches and seizures, shall not be violated, and no Warrants shall issue, but upon probable cause, supported by Oath or affirmation, and particularly describing the place to be searched, and the persons or things to be seized." (emphasis mine). Thus reasonable searches and seizures, especially those authorized by a warrant, are constitutional.
Furthermore, even in light of a constitutional right of privacy derived from this statue, depending on how the "search history" is compiled, the 4th Amendment might not even apply, due to the Katz doctrine, also known as the "open fields" doctrine. Basically, the 4th amendment (as far as searches goes) does not apply to things that are publicly observable; while this would protect a literal "search history" compilation (baring a reasonable search), the searches themselves are public queries, broadcasted over the internet. Anyone watching could compile them into a "search history" themselves.
