You are standing on a road in Death Valley, California. The temperature is 119F, and you have no water. You do know that water is located somewhere along the road, but you are disoriented from the heat, and do not know in which direction or how far. You have no vehicle – you have to walk to find the water. The road is perfectly straight.
Give an algorithm for finding the water where you walk distance of no more than 9x, under the assumption that the water is located at distance x from you. Also explain why your method does not exceed 9x in the distance walked.
Remember: you do not know the value of x nor the direction that x lies from you.
Conspiracy for Good