Introduction

The infinite-wall door problem asks how to find one target location when search space has no known boundary. A one-direction walk can fail forever if the target is on the other side. The standard solution is an expanding search pattern that guarantees discovery with bounded overhead.

Problem Model

Assume positions on the wall are integer coordinates and you start at zero. A hidden door exists at unknown coordinate d, which can be positive or negative. Your algorithm can probe positions and ask whether the door is there.

A correct strategy must satisfy two goals:

• Completeness: door is always found eventually.
• Efficiency: travel or probe count grows reasonably with distance.

Why Simple Strategies Fail

Linear one-side scan is incomplete on unbounded two-sided space. Symmetric small-step zig-zag is complete, but inefficient for distant targets because it revisits near positions too often.

Exponential expansion solves this tradeoff by doubling search radius each phase.

Exponential Alternating Search

Probe sequence can be:

• +1
• -2
• +4
• -8
• +16

Distance doubles and direction alternates, so both sides are covered quickly.

1def find_door(is_door):
2    if is_door(0):
3        return 0
4
5    radius = 1
6    while True:
7        right = radius
8        if is_door(right):
9            return right
10
11        left = -2 * radius
12        if is_door(left):
13            return left
14
15        radius *= 2

This formulation assumes direct probing. If movement cost matters, you can still use the same boundary schedule but account for travel path between probes.

Complexity Intuition

Let absolute door distance be n. Once search radius exceeds n, the door must be inside explored range on one side. Number of phases is proportional to log distance, and total probe operations remain proportional to distance with a constant-factor overhead.

This is much better than linear growth in revisit-heavy patterns.

Practical Variant with Continuous Movement

In robotics or games, movement cost can dominate probe count. You can keep current position and move to each new checkpoint rather than teleporting conceptually. Log both metrics:

• Probe count.
• Total travel distance.

1def checkpoints(phases):
2    r = 1
3    out = []
4    for _ in range(phases):
5        out.append(r)
6        out.append(-2 * r)
7        r *= 2
8    return out
9
10print(checkpoints(5))

This utility helps test navigation code before integrating sensors.

Using Side Information

If you know the door is only on one side, you can do one-direction exponential search and then binary search inside the first interval that brackets the target condition. That reduces travel and probes.

If you only have probabilistic side hints, bias the order but preserve fallback coverage. Completeness should not depend on uncertain assumptions.

Simulation for Validation

Before deployment, simulate random door positions and compare strategies.

1import random
2
3
4def probes_for(door):
5    if door == 0:
6        return 1
7    r, probes = 1, 1
8    while True:
9        probes += 1
10        if r == door:
11            return probes
12        probes += 1
13        if -2 * r == door:
14            return probes
15        r *= 2
16
17samples = [probes_for(random.randint(-1000, 1000)) for _ in range(5000)]
18print('avg', sum(samples) / len(samples))
19print('max', max(samples))

Simulation reveals constant factors and helps choose between theoretically correct variants.

Common Pitfalls

• Searching one direction only on a two-sided infinite domain.
• Expanding radius linearly instead of exponentially.
• Ignoring movement cost when implementing in physical systems.
• Forgetting to probe start position before expansion.
• Measuring only average case and ignoring worst-case guarantees.

Summary

• Infinite two-sided search needs guaranteed coverage strategy.
• Exponential alternating expansion gives completeness with bounded overhead.
• Doubling radius is the key to efficient distant-target discovery.
• Adapt algorithm for movement cost when probes are not free.
• Validate behavior with simulation before production use.