# Finding an object on an arbitrarily large line

There is an arbirarly long line of unknown size. You are standing at a particular point you can either move 1 step forward or 1 step backward. You have to search for an object in that line. Your object can be in any direction. Give an optimal solution.

A search might be 1 step forward, 2 back and so on.

Can you do better than that? What would be an efficient search pattern?

• arbirarly long line of unknown size Do you mean a finite segment? – dxiv Dec 2 '16 at 3:26

I don't have a proof, but strongly suspect it will be hard to beat going to one end of the segment, then turning around and going to the other end. A good measure of efficiency is the total number of steps taken over all the possible locations of the object. If you are $a$ from the end in the direction you start out and $b$ from the other end this results in $\frac 12a(a-1)+2ab+\frac 12b(b-1)$, with the first term representing the sums of the distances in the direction you start out, the $2ab$ being the $b$ cases of going $a$ to one end and $a$ back, and the last term the sum of the distances after you get back to start. You did not specify your strategy after the first three steps, but you have already had one case where you know you will not find the object and presumably have two more to come after you turn around again.