算法：墙上的门

题目：你面前是一堵朝两个方向无限延伸的墙。墙上有一扇门，但你不知道门离你有多远，也不知道门位于哪个方向。你只有走到门面前才能看到它。假设从当前位置到门要走n（事先不知道n的大小）步，请设计一个算法，使你最多走O(n)步就能遇到门。

【初步分析】

分析题目，已知墙上有两个方向，所以并不能只朝一个方向去找门，我们得先向钟摆一样来回找，先走一边走几步之后在返回起点继续朝另外一边走，我们不需要判断门在哪一边，我们只需要遇到门就可以。

【题目解法】

尝试以每次乘以2的方式递进。

第一次：往右走2步，回起点，往左走2步，回起点。

第二次：往右走4步，回起点，往左走4步，回起点。

设一个变量i，起步从起点开始，也就是以0开始。

首先往右走2^i步，往左走2^i步；

然后往右走2^(i+1)步，往左走2^(i+1)步

距离为n步，所以可以得出2^(i-1)<n≤2^i

差不多最多要走4×（2^0+2^1+……+2^（i-1）+3×2^i

即4×（2^i-1）+3×2^i=14×2^（i-1）<14*n

最多能保证O(n)步就能遇到门