I am given this problem and not quite sure how to approach it.
I was thinking maybe the best way is to go 1km east then 2km west then 3km easy... and so on until we reach the exit.
We are standing in the middle on a tunnel that goes left-right. At some unknown number of K kilometers from us, is the exit. We do not know whether the exit is located in east or west. Neither do know the distance K to the exit.
We want to walk to the in as few days as possible. Assume we can walk 50 kilometers each day. Give an algorithm that will ensure we reach the exit in O(K) days. Argue that your algorithm is correct. Explain your algorithm on an example.
You are on the right track. You need to oscillate between going east and west but instead of increasing the amplitude by one, double it each time.
This will ensure that you reach the exit in O(K) days. This is because, if K is 2^p, then before reaching the exit, you would have travelled at the most O(2^p) km.
Ex: If K = 2^n + 1, the worst case can be:
1
1 + 2
2 + 4
4 + 8
8 + 16
...
2^(n) + 2^(n+1)
2^(n+1) + 2^n + 1
(O (9K) ).