你面对着一堵墙，左右2边都无限长

墙上有一扇门，有可能在左边也有可能在右边，你只有站在门前才能看到这扇门

求找这扇门最有效率的算法 O(n)，门离你初始位置有n步

我的做法是 0 1 -1 2 -2 3 -3 。。这样一直找下去

不知道对不对，请教


付上原题，希望没有理解错误

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.

你的想法应该是对的，
这其实跟找迷宫的出口差不多，只不过它只有两个方向．
其实也就是广度优先搜索．

这样也能算最快???

楼上的有什么好的建议吗？

[QUOTE]0 1 -1 2 -2 3 -3 [/QUOTE]

这种方法应该是可以的..不过为了减少时间.须使用临时变量记载上次步子的位置..

OK。多谢回答

顺便说一下，2楼的说这是广度优先搜索，其实并不是
广度优先搜索指的是，比如在树中，先把一层节点搜索完后再进行下一层的搜索，而深度优先搜索就是把一个节点不断扩展搜索下去，直到叶节点，然后再返回其父节点重复这种动作
一般来说广度优先搜索适合用来求解一些最短路径或者最短操作数之类的问题，而深度优先搜索除了编程比较简单之外实在想不出有什么优势，而许多更高级的算法是一些判断的函数结合进这两种搜索之中，比如迭带加宽、迭带加深、启发式搜索等

大家都是推测罢了,虽然我也认为这种方法不错,但有没有谁可以从理论上证明一下它就是最有效的呢?毕竟"口说无凭"么

这题楼主的做法其实就是先把距离是1的一层节点搜索完后再进行距离是2的一层的搜索,(1 -1, 2 -2, 3 -3 );
怎么不是广搜?

这明显不是最快的，最快的算法是0，1，-2，4，-8，16，。。。
0 1 -1 2 -2 3 -3 。。这种算法复杂度为n*（2n-1），也即O（n^2)
而0，1，-2，4，-8，16，。。。，这种算法复杂度为3n-2，也即O（n）
明显是0，1，-2，4，-8，16，。。。快！！！