I thought the expression was "to search from land to sea" but according to Google, I'm wrong.
What's the correct expression?
After searching his jacket __, he gave up hope.
Search high and low (for something):
to try very hard to find something look high and low (for something)
- Janet searched high and low, but she couldn't find the kitten and finally had to ask the man.
(Cambridge Dictionary of American Idioms)
To search every nook and cranny.
From Cambridge Dictionary:
Every nook and cranny – every part of a place.
If you want to use this with the object of a search, you need to use prepositions:
After searching for his jacket in every nook and cranny ...
After searching every nook and cranny for his jacket ...
Another equally good word for it is, I think, the verb to comb:
3 Search carefully and systematically.
But the best way in which you can express the thoroughness of your search is, in my opinion, the phrase to leave no stone unturned, which is also idiomatically appropriate for your quest:
Try every possible course of action in order to achieve something.
In computer science we often use the term Exhaustive Search
One idiom for this is
The auditors went over the records with a fine-toothed comb.
This is most appropriate when you want to emphasize that the search paid attention to fine details. For example, when searching for some missing papers you didn't just glance over the bookshelf for missing papers, but you checked between every pair of books, or even flipped through each book.
an attitude or system of thorough searching or scrutinizing
(google search seems to indicate that both "fine-toothed" and "fine-tooth" are used)
Although all top google searches listed for this option are related to the Pokémon theme song, I believe "to search far and wide” could also be used in this situation.
After searching far and wide for his jacket, he gave up hope.
Although, it may not be the very best (like no-one ever was).
"Everywhere" or "Looked/Searched everywhere"
After looking everywhere for his jacket, he gave up hope.
After searching everywhere for his jacket, he gave up hope.
is probably normal usage.
Closest I can think of to your "from land to sea" would probably be "over hill and dale" but that's not common usage - and certainly not describing something indoors.
Despite searching over hill and dale, they couldn't find a suitable campsite.
Thoroughly would fit well in the sentence as written.
This also implies that the search was rigorous and complete.
A similar wording often used for missing planes or people is to search on land and sea.
Example from a news story:
Philippine forces searched on land and sea Thursday but were unable to find any sign...