Door and the wall

You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you do not know how far away the door is and in which direction. You can see the door only when you are right next to it. How do you reach the door by walking at most O(n) steps where n(unknown to you) is the number of steps between your initial position and the door.

Will the order change if you had sequential / random access to the pathway ? That is, for a sequential pathway, you will have to walk from position 1 to 17 using the path 1-2-3-4...-17. For random access you may visit point 17 from point 1 directly without accessing elements 2->16.

Door and wall: