You don't understand that news item. The police didn't search a specific person's account, they asked Google (who gave it to them voluntarily) anyone who searched the victim's address in the past week. Nothing unconstitutional about that.
But yes, I'm aware of the Third Party doctrine ruled on by judges whose conception of people making phone calls involved an individual talking to another human being (a.k.a. an operator) to connect you to who you wanted to talk to.
A practice antiquated when the ruling was made and a bygone relic by this point.
My complaint is that Google should not have been permitted that choice in the first place. The entire sequence of events - from requesting the data without a warrant through to handing the data over without a warrant and any following data mining that was done with it should have been forbidden on constitutional grounds. Both parties ought to have been in violation of the law here. We need to fix the gaping hole in our constitutional rights that the third party doctrine represents.