Door in a wall You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you know neither how far away nor in which direction. You can see the door only when you are right next to it. Design an algorithm that enables you to reach the door by walking at most O(n) steps where n is the (unknown to you) number of steps between your initial position and the door. [Par95]
The correct answer and explanation is:
Algorithm to Find the Door in the Wall in O(n) Steps
Strategy:
The key challenge in this problem is that you do not know the distance or direction of the door. A naïve approach would be to randomly pick a direction and walk indefinitely, but that could be inefficient. Instead, an exponential search strategy ensures you find the door in at most O(n) steps.
Algorithm (Two-Phase Strategy):
- Exploration Phase (Exponential Search):
- Move 1 step right.
- Then move 2 steps left.
- Then move 4 steps right, 8 steps left, and so on, doubling the step size each time.
- Continue until you find the door.
- Linear Search Phase (Backtracking):
- Once you’ve bounded the location of the door (i.e., you’ve stepped past it in one direction), perform a linear search within that bounded range to find the exact position.
Explanation:
Step-by-Step Execution
- Suppose the door is n steps to the right.
- Your first step is 1 step right (if the door is here, stop).
- Then move 2 steps left (you are now at -1).
- Then move 4 steps right (you are now at position 3).
- Then move 8 steps left (you are now at position -5).
- Continue doubling the step size each time.
Eventually, you will either:
- Land exactly on the door (in which case, you’re done).
- Step past the door (meaning you have bounded its location).
Once you’ve bounded the door’s location between two points a and b, where a < door < b, perform a simple linear search between these points. The total steps taken will be at most O(n).
Proof of O(n) Complexity
- The exponential phase covers distance 1 + 2 + 4 + … + 2^k, where k is the smallest integer such that 2^k ≥ n. This sum is O(n).
- The linear search phase takes at most O(n) additional steps.
- Since the total steps are at most O(n) + O(n) = O(n), the solution is optimal.
This ensures you reach the door in at most O(n) steps regardless of its position.