Algorithm for finding a mouse hole in a wall in O(n) time
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.