Think footprints.
They aren’t searching his device.
They are looking at the “pings” that his device has left behind on his route.
His device is communicating with mobile phone towers.
Actually, they don’t have to check cell tower pings. Android devices report their GPS location to Google by default.
I saw a show 3 or 4 years ago — Stossel, I think — and he got a Google printout of his day(s). Some of the time the phone was turned off. It went so far as to tell where he stopped and got out of the car (a taxi, I think) at museums or similar. IIRC, it was more than triangulation among towers.
> Think footprints <
That is an interesting analogy. But you have no expectation of privacy when it comes to making footprints. You do have an expectation of privacy when it comes to anything regarding your cell phone use.