Algorithm for finding a mouse hole in a wall in O(n) time

There is this question:


As a result of the US Election, a wall is built along the entire Canadian border. You have been told
there is a mouse hole in the wall, but it can only be seen when you are standing in front of it. Your
task is to find the mouse hole by walking along the wall; however, you are standing in Minnesota
and do not know whether the hole is East or West of your current location.


Give an algorithm that will allow you to find the mouse hole in O(n) steps, where n is the (unknown
to you) distance in steps from your initial location to the mouse hole.

I was thinking that to find the mouse hole in O(n) steps, I would have to go both East and West at the same time.

But seeing that I can't do this (or maybe I can?), I thought that regardless of direction I first take since I'm traveling around the US border and then around the Canadian border, I would have traveled a linear time. I'm also thinking that this problem might resemble a graph?

How can I go about writing an algorithm to describe this?

This problem goes by various names, including the linear search problem and the cow path problem. The solution indicated in Denis's answer is optimal for deterministic algorithms (though the competitive ratio is 9 rather than 8), but randomized algorithms can do almost twice as better; see Kao, Rife and Tate.

StackExchange Computer Science Q#52772, answer score: 3