Classic Problem

Here's a famous problem (featured on the cover of Parberry's book) to give you something to think about during the term break:

Suppose you are standing in front of a brick wall which extends infinitely far in both directions. Somewhere in the wall there is a door, but you do not know whether it is to your right or to your left. It's dark - the only way you will find the door is when you are standing right in front of it.

Give an O(n) algorithm to find the door, where n is the (unknown) distance from your starting position to the position of the door.