It might be involved more with search algorithm but I cannot think of any of them. Here is the problem:
You are in a corridor that stretches infinitely in both directions. Your room is somewhere along the corridor, but you don't know how far away or even in which direction it is. You won't know if you have reached your room until you are right in front of 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 your room.
The problem is, current position is in middle if I choose to go left and till end does not find my room, I must come back all the way until first position which is already n steps!
Start by running $1$ step right, then $2$ steps left, then $4$ steps right and so on. Assume that you hit your room at step $1 + 2 + 4 + \dots + 2^{m-1} + k$, $2^{m-1} < k \le 2^m$. Then we have used $2^{m} - 1 + k$ steps in total, and we are at $$n = \sum_{j=0}^{m-1} (-1)^j 2^{j} + (-1)^m k = \frac{1 - (-2)^{m}}{3} + (-1)^m k.$$ Therefore $|n| \ge k - \frac{1}{3} 2^{m} - \frac{1}{3} > 2^{m-1} - \frac{2}{3} 2^{m-1} = \frac{1}{3} 2^{m-1}$. In particular $2^m - 1 + k \le 2^{m+1} - 1 < 12 |n|$, so we have used $O(|n|)$ steps.